算法笔记_037:寻找和为定值的两个数（Java）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

目录
1 问题描述
2 解决方案
2.1 排序夹逼法

1 问题描述

输入一个整数数组和一个整数，在数组中查找两个数，满足他们的和正好是输入的那个整数。如果有多对数的和等于输入的整数，输出任意一对即可。例如，如果输入数组[1,2,4,5,7,11,15]和整数15，那么由于4+11 = 15，因此输出4和11。

2 解决方案

2.1 排序夹逼法

首先将整数数组，使用合并排序进行从小打到的排序，然后对这个排完序的数组从两头往中间遍历，一旦出现两个数的和等于输入的那个整数，则立即输出这两个数，并结束遍历。

具体代码如下：

package com.liuzhen.array_2;public class TwoSumN {
/*
* 参数A：给定的一个从小到大排序的数组
* 参数n:待求和数n
* 函数功能：打印出A中两个元素，满足A[i]+A[j] = n
*/
public void getTwoSumN(int[] A,int n){
int start = 0;
int end = A.length - 1;
while(start < end){
if(A[start] + A[end] == n){
System.out.println("\n数组中元素A["+start+"]" +
" + A["+end+"] = "+n+",A["+start+"] = "+A[start]+",A["+end+"] = "+A[end]);
break;
}
else{
if(A[start] + A[end] > n)
end--;
else
start++;
}
}
} //归并排序
public void mergeSort(int[] A){
if(A.length > 1){
int[] leftA = getHalfArray(A,0); //数组A的左半部分
int[] rightA = getHalfArray(A,1); //数组A的右半部分
mergeSort(leftA);
mergeSort(rightA);
getMerge(A,leftA,rightA);
}
} /*
* 参数A：要进行折半的数组
* 参数judge:judge == 0表示返回数组A左上半部分，judge != 0表示返回数组A的右半部分
* 函数功能：把数组按照长度均分为上半部分和下半部分
*/
public int[] getHalfArray(int[] A,int judge){
int[] result;
if(judge == 0){
result = new int[A.length/2];
for(int i = 0;i < A.length/2;i++)
result[i] = A[i];
}
else{
result = new int[A.length - A.length/2];
for(int i = 0;i < A.length - A.length/2;i++)
result[i] = A[i+A.length/2];
}
return result;
}
/*
*参数A：给定待排序数组
*参数leftA:数组A的左半部分
*参数rightA:数组的右半部分
*函数功能：返回数组A的从小到大排序
*/
public void getMerge(int[] A,int[] leftA,int[] rightA){
int i = 0; //用于计算当前遍历leftA的元素个数
int j = 0; //用于计算当前遍历rightA的元素个数
int count = 0; //用于计算当前得到按从小到大排序的A的元素个数
while(i < leftA.length && j < rightA.length){
if(leftA[i] < rightA[j]){
A[count++] = leftA[i];
i++;
}
else{
A[count++] = rightA[j];
j++;
}
}
if(i < leftA.length){
while(i < leftA.length)
A[count++] = leftA[i++];
}
if(j < rightA.length){
while(j < rightA.length)
A[count++] = rightA[j++];
}
} public static void main(String[] args){
TwoSumN test = new TwoSumN();
int[] A = {2,1,7,4,6,1,2,4,3,6,8,4,2,1,7,3,4,6,8,3,4};
test.mergeSort(A);
System.out.println("对数组A进行合并排序后结果：");
for(int i = 0;i < A.length;i++)
System.out.print(A[i]+" ");
test.getTwoSumN(A, 10);
}
}