Java 找到数组中两个元素相加等于指定数的所有组合

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

思路1：可以用hash表来存储数组中的元素，这样我们取得一个数后，去判断sum - val 在不在数组中，如果在数组中，则找到了一对二元组，它们的和为sum，该算法的缺点就是需要用到一个hash表，增加了空间复杂度。

思路2：同样是基于查找，我们可以先将数组排序，然后依次取一个数后，在数组中用二分查找，查找sum -val是否存在，如果存在，则找到了一对二元组，它们的和为sum，该方法与上面的方法相比，虽然不用实现一个hash表，也没不需要过多的空间，但是时间多了很多。排序需要O(nLogn)，二分查找需要(Logn)，查找n次，所以时间复杂度为O(nLogn)。

思路3：该方法基于第2种思路，但是进行了优化，在时间复杂度和空间复杂度是一种折中，但是算法的简单直观、易于理解。首先将数组排序，然后用两个指向数组的指针，一个从前往后扫描，一个从后往前扫描，记为first和last，如果 fist + last < sum 则将fist向前移动，如果fist + last > sum，则last向后移动。

第三种思路是最好的。

public class Main {
public static void main(String[] args) {
int[] array1 = {10,2,7,4,5,6,3,8,9,1};
int[] array2 = {1,2,3,4,5,6,7,8,9,10};
int[] array3 = {1,2,3,4,5,6,7,8,9,10};
// execute1(array1, 8);
// execute2(array2, 8);
execute3(array3, 10);
} //思路：使用hash表存储数组各元素是否存在的标志，然后遍历数组，判断sum与当前数组元素的差值是否在hash表中,
//若为真则打印，该算法不要求数组有序，但要求一个hash数组的额外空间，时间复杂度是O(n)
private static void execute1(int[] array, int m) {
int size = array.length;
int hash[] = new int[size];
for(int i = 0; i < size; i++) {
hash[array[i]%size] = 1;
} for(int i = 0; i < size; i++) {
int tmp = m - array[i];
if((tmp > array[i]) && (hash[tmp%size] == 1)){
System.out.println(array[i] + " " + tmp);
}
}
} //思路：该方法的前提是要求数组是有序的，然后再遍历数组，判断sum与数组元素的差值是否在数组中，由于数组有序所以可以采用二分查找的方法
//二分查找的时间复杂度为O(logn),排序的时间复杂度是O(nlogn),查找n次，总的时间复杂度为O(nlogn)，避免了空间的浪费
private static void execute2(int[] array, int m) {
for(int i = 0; i < array.length; i++) {
int tmp = m - array[i];
if (tmp > array[i]) {
if (binarySearch(array, tmp) != -1) {
System.out.println(array[i] + " " + tmp);
}
}
}
}
private static int binarySearch(int[] array, int key) {
if (array.length == 0) {
return -1;
} int first = 0;
int last = array.length -1; int mid;
while(first <= last) {
mid = (first + last) / 2;
if (array[mid] == key) {
return mid;
} else if (array[mid] < key) {
first = mid + 1;
} else {
last = mid -1;
}
}
return -1;
} //思路：该方法的前提是要求数组是有序的，使用两个指针，分别指向最后一个元素和第一个元素，判断它们的和是否等于sum，若等于则打印，并且first向前移动，last也向前移动
//若它们的和小于sum，则说明first太小了，需要first向前移动，若它们的和大于sum，则说明last太大了，需要last向前移动，直到last>=first
private static void execute3(int[] array, int m) {
int first = 0;
int last = array.length -1;
int sum = 0;
while(first < last ) {
sum = array[first] + array[last];
if (sum == m) {
System.out.println(array[first] + " " + array[last]);
first++;
last--;
} else if (sum < m) {
first++;
} else {
last--;
}
}
}
}