1. package com.algorithm.hash;  
2.   
3. public class alg1 {  
4.     public static void main(String argv[]) {  
5.         int[] array1 = {10,2,7,4,5,6,3,8,9,1};  
6.         int[] array2 = {1,2,3,4,5,6,7,8,9,10};  
7.         int[] array3 = {1,2,3,4,5,6,7,8,9,10};  
8.         alg1.execute1(array1, 8);  
9.         alg1.execute2(array2, 8);  
10.         alg1.execute3(array3, 8);  
11.     }  
12.       
13.     //思路：使用hash表存储数组各元素是否存在的标志，然后遍历数组，判断sum与当前数组元素的差值是否在hash表中,  
14.     //若为真则打印，该算法不要求数组有序，但要求一个hash数组的额外空间，时间复杂度是O(n)  
15.     private static void execute1(int[] array, int m) {  
16.         int size = array.length;  
17.         int hash[] = new int[size];  
18.         for(int i = 0; i < size; i++) {  
19.             hash[array[i]%size] = 1;  
20.         }  
21.           
22.         for(int i = 0; i < size; i++) {  
23.             int tmp = m - array[i];  
24.             if((tmp > array[i]) && (hash[tmp%size] == 1)){  
25.                 System.out.println(array[i] + " " + tmp);  
26.             }  
27.         }  
28.     }  
29.       
30.     //思路：该方法的前提是要求数组是有序的，然后再遍历数组，判断sum与数组元素的差值是否在数组中，由于数组有序所以可以采用二分查找的方法  
31.     //二分查找的时间复杂度为O(logn),排序的时间复杂度是O(nlogn),查找n次，总的时间复杂度为O(nlogn)，避免了空间的浪费  
32.     private static void execute2(int[] array, int m) {  
33.         for(int i = 0; i < array.length; i++) {  
34.             int tmp = m - array[i];  
35.             if (tmp > array[i]) {  
36.                 if (binarySearch(array, tmp) != -1) {  
37.                     System.out.println(array[i] + " " + tmp);  
38.                 }  
39.             }  
40.         }  
41.     }  
42.     private static int binarySearch(int[] array, int key) {  
43.         if (array.length == 0) {  
44.             return -1;  
45.         }  
46.           
47.         int first = 0;  
48.         int last = array.length -1;  
49.           
50.         int mid;  
51.         while(first <= last) {  
52.             mid = (first + last) / 2;  
53.             if (array[mid] == key) {  
54.                 return mid;  
55.             } else if (array[mid] < key) {  
56.                 first = mid + 1;  
57.             } else {  
58.                 last = mid -1;  
59.             }  
60.         }  
61.         return -1;  
62.     }  
63.       
64.     //思路：该方法的前提是要求数组是有序的，使用两个指针，分别指向最后一个元素和第一个元素，判断它们的和是否等于sum，若等于则打印，并且first向前移动，last也向前移动  
65.     //若它们的和小于sum，则说明first太小了，需要first向前移动，若它们的和大于sum，则说明last太大了，需要last向前移动，直到last>=first  
66.     private static void execute3(int[] array, int m) {  
67.         int first = 0;  
68.         int last = array.length -1;  
69.         int sum = 0;  
70.         while(first < last ) {  
71.             sum = array[first] + array[last];  
72.             if (sum == m) {  
73.                 System.out.println(array[first] + " " + array[last]);  
74.                 first++;  
75.                 last--;  
76.             } else if (sum < m) {  
77.                 first++;  
78.             } else {  
79.                 last--;  
80.             }  
81.         }  
82.     }  
83.      
    

java实现 数组中两个元素相加等于指定数的所有组合,布布扣,bubuko.com

java实现 数组中两个元素相加等于指定数的所有组合