给定一个未排序的整数数组，找到一对给定的和

例如，

输入：

arr=[8,7,2,5,3,1]

sum=10

输出：

对发现在索引0和2（8+2）

or

对发现在索引1和4（7+3）

 

方法一：原始的方法

　　c语言：

1 #include 
     
       2 #include 
      
        3  4 //使用给定的和找到一个数组中的一对的原始方法 5 void findPair(int arr[], int n, int sum) 6 { 7     for (int i = 0; i < n - 1; i++) 8     { 9         for (int j = i + 1; j < n; j++)10         {11             // 找到这样的对，打印并返回12             if (arr[i] + arr[j] == sum)13             {14                 printf("Pair found at index %d and %d", i, j);15                 return;16             }17         }18     }19 20     //在数组中不存在给定和的对21     printf("Pair not found");22 }23 24 int main()25 {26     int arr[] = { 8, 7, 2, 5, 3, 1 };27     int sum = 10;28 29     int n = sizeof(arr) / sizeof(arr[0]);30     //printf("%d\n",n);31 32     findPair(arr, n, sum);33 34     system("pause");35     return 0;36 }
      
     

　　java：

1 package 排列; 2  3 public class FindPair{ 4     public static void findPair(int arr[], int sum){ 5         int n = arr.length; 6  7         for (int i = 0; i < n - 1; i++){ 8              9             for (int j = i + 1; j < n; j++){10                 11                 if (arr[i] + arr[j] == sum){12                     System.out.println("Pair found at index " + i + " and " + j);13                     return;14                 }15             }16         }17         18         System.out.println("Pair not found");19     }20 21 22     public static void main (String[] args)23     {24         int arr[] = { 8, 7, 2, 5, 3, 1 };25         int sum = 10;26           27         findPair(arr, sum);28     }29 }

输出：

　　在索引0和2找到的对

 

上述解的时间复杂度为O（n^2），程序使用的辅助空间为O（1）

 

方法2：使用O(nlogn)排序法

　　这个想法是按照升序对给定的数组进行排序，并通过维持最初指向数组的两个端点的两个索引（低和高）来维护搜索空间。

　　c语言：

1 #include 
     
       2 using namespace std; 3  4 //使用排序在给定的数组中找到一个数组的函数 5 void findPair(int arr[], int n, int sum) 6 { 7     //升序排序 8     sort(arr, arr + n); 9 10     //维护指向数组终点的两个索引11     int low = 0;12     int high = n - 1;13 14     //在循环的每次迭代中减少搜索空间arr [low..high]15     //循环直到低小于高16     while (low < high)17     {18         if (arr[low] + arr[high] == sum)19         {20             cout << "Pair found ";21             return;22         }23 24         //如果total小于期望的总和，则递增低索引25         //递减高指数是总和多于总和26         (arr[low] + arr[high] < sum) ? low++ : high--;27     }28 29     cout << "Pair not found";30 }31 32 int main()33 {34     int arr[] = { 8, 7, 2, 5, 3, 1 };35     int sum = 10;36 37     int n = sizeof(arr) / sizeof(arr[0]);38 39     findPair(arr, n, sum);40 41     system("pause");42     return 0;43 }
     

　　java语言：

1 package 排列; 2  3 import java.util.Arrays; 4  5 public class FindPair2 6 { 7     public static void findPair(int arr[], int sum) 8     { 9         Arrays.sort(arr);10 11         int low = 0;12         int high = arr.length - 1;13      15         while (low < high)16         {17             if (arr[low] + arr[high] == sum)18             {19                 System.out.println("Pair found");20                 return;21             }22      23             if (arr[low] + arr[high] < sum)24                 low++;25             else26                 high--;27         }28      29         System.out.println("Pair not found");30     }31 32     public static void main (String[] args)33     {34         int arr[] = { 8, 7, 2, 5, 3, 1 };35         int sum = 10;36           37         findPair(arr, sum);38     }39 }

 

输出：

　　找到对

 

上述解的时间复杂度为O（nlogn），程序使用的辅助空间为O（1）

 

方法3：为O(n)使用散列

　　这个想法是将数组arr[i]的每一个元素插入map中。我们还可以检查map中是否存在差异(arr[i],sum-arr[i])

　　c语言：

1 #include 
     
       2 using namespace std; 3  4 // 使用散列map 5 void findPair(int arr[], int n, int sum) 6 { 7     unordered_map
      
        map; 8  9     for (int i = 0; i < n; i++)10     {11         //检查对（arr [i]，sum-arr [i]）是否存在12 13         //如果差异见于之前，打印对14         if (map.find(sum - arr[i]) != map.end())15         {16             cout << "Pair found at index " << map[sum - arr[i]] << " and " << i;17             return;18         }19 20         //在map中存储当前元素的索引21         map[arr[i]] = i;22     }23 24     cout << "Pair not found";25 }26 27 int main()28 {29     int arr[] = { 8, 7, 2, 5, 3, 1 };30     int sum = 10;31 32     int n = sizeof(arr) / sizeof(arr[0]);33 34     findPair(arr, n, sum);35 36     system("pause");37     return 0;38 }
      
     

 

　　java语言：

1 package 排列; 2  3 import java.util.HashMap; 4 import java.util.Map; 5  6 public class FindPair3 7 { 8     public static void findPair(int arr[], int sum) 9     {10         Map
     
       map = new HashMap
      
       ();11      12         for (int i = 0; i < arr.length; i++)13         {14      15             if (map.containsKey(sum - arr[i]))16             {17                 System.out.println("Pair found at index " + 18                         map.get(sum - arr[i]) + " and " + i);19                 return;20             }21      22             map.put(arr[i], i);23         }24 25         System.out.println("Pair not found");26     }27 28     public static void main (String[] args)29     {30         int arr[] = { 8, 7, 2, 5, 3, 1 };31         int sum = 10;32           33         findPair(arr, sum);34     }35 }
      
     

输出：

　　在索引0和2找到的对

 

上述解的时间复杂度为O（n），程序使用的辅助空间为O（n）