给定一个整型数组，数组未排序，请找出一对数，使这两个数的和等于一个给定的值。 例如， 输入: arr = [8, 7, 2, 5, 3, 1] sum = 10
输出: Pair found at index 0 and 2 (8 + 2) 或 Pair found at index 1 and 4 (7 + 3)
傻瓜式方法比较粗暴，通过遍历给定数组中的所有两个数字组成的组合，只要发现一个组合的和等于期望中的数字，就返回它们。
C语言实现：
#include <stdio.h> // Naive method to find a pair in an array with given sum void findPair(int arr[], int n, int sum) { // consider each element except last element for (int i = 0; i < n - 1; i++) { // start from i'th element till last element for (int j = i + 1; j < n; j++) { // if desired sum is found, print it and return if (arr[i] + arr[j] == sum) { printf("Pair found at index %d and %d", i, j); return; } } } // No pair with given sum exists in the array printf("Pair not found"); } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; }Java语言实现： class FindPair { // Naive method to find a pair in an array with given sum public static void findPair(int arr[], int sum) { // n is length of the array int n = arr.length; // consider each element except last element for (int i = 0; i < n - 1; i++) { // start from i'th element till last element for (int j = i + 1; j < n; j++) { // if desired sum is found, print it and return if (arr[i] + arr[j] == sum) { System.out.println("Pair found at index " + i + " and " + j); return; } } } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } }输出： Pair found at index 0 and 2
这种解决方案的时间复杂度是 O(n2)，空间复杂度是O(1)。
这种方法的观点是，先对数组进行排序，然后通过两个索引index（高high和低low）来进行搜索。在初始状态时，这两个索引index分别指向数组的首尾（假设数组长度为n，low指向第0个元素，high指向第n-1个元素）。然后我们不断地逼近low和high的值来搜索数组arr[low...high]，直到low大于或等于high。在这个过程中，我们计算arr[high]与arr[low]之和，并与给定的数字比较，如果和小于给定数字，就增加low的值，反之则减少high的值。最后，如果在数组中找到了这一对数字，返回它们即可。
C++语言实现：
#include <bits/stdc++.h> // Function to find a pair in an array with given sum using Sorting void findPair(int arr[], int n, int sum) { // sort the array in ascending order std::sort(arr, arr + n); // maintain two indexes pointing to end-points of the array int low = 0; int high = n - 1; // reduce search space arr[low..high] at each iteration of the loop // loop till low is less than high while (low < high) { // sum found if (arr[low] + arr[high] == sum) { std::cout << "Pair found"; return; } // increment low index if total is less than the desired sum // decrement high index is total is more than the sum (arr[low] + arr[high] < sum)? low++: high--; } // No pair with given sum exists in the array std::cout << "Pair not found"; } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1}; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } java语言实现： import java.util.Arrays; class FindPair { // Naive method to find a pair in an array with given sum public static void findPair(int arr[], int sum) { // sort the array in ascending order Arrays.sort(arr); // maintain two indexes pointing to end-points of the array int low = 0; int high = arr.length - 1; // reduce search space arr[low..high] at each iteration of the loop // loop till low is less than high while (low < high) { // sum found if (arr[low] + arr[high] == sum) { System.out.println("Pair found"); return; } // increment low index if total is less than the desired sum // decrement high index is total is more than the sum if (arr[low] + arr[high] < sum) low++; else high--; } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } }输出: Pair found
这种解决方案的时间复杂度是 O(nlogn)，空间复杂度是 O(1)。
其实，我们可以在线性的时间内解决问题，解决方案的关键在于使用map。算法就是把数组中的元素arr[i]插入到map中。在遍历数组过程中，我们需要查找sum - arr[i]是否在数组中。如果能找到，就打印出arr[i]和sum-array[i]，返回。
C++语言实现：
#include <bits/stdc++.h> using namespace std; // Function to find a pair in an array with given sum using Hashing void findPair(int arr[], int n, int sum) { // create an empty map unordered_map<int, int> map; // do for each element for (int i = 0; i < n; i++) { // check if pair (arr[i], sum-arr[i]) exists // if difference is seen before, print the pair if (map.find(sum - arr[i]) != map.end()) { cout << "Pair found at index " << map[sum - arr[i]] << " and " << i; return; } // store index of current element in the map map[arr[i]] = i; } // we reach here if pair is not found cout << "Pair not found"; } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1}; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } java语言实现： import java.util.HashMap; import java.util.Map; class FindPair { // Naive method to find a pair in an array with given sum public static void findPair(int arr[], int sum) { // create an empty Hash Map Map<Integer, Integer> map = new HashMap<Integer, Integer>(); // do for each element for (int i = 0; i < arr.length; i++) { // check if pair (arr[i], sum-arr[i]) exists // if difference is seen before, print the pair if (map.containsKey(sum - arr[i])) { System.out.println("Pair found at index " + map.get(sum - arr[i]) + " and " + i); return; } // store index of current element in the map map.put(arr[i], i); } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } }输出： Pair found at index 0 and 2
这种方案的时间复杂度和空间复杂度都是O(n)。
练习： 打印出数组中所有和等于给定值的数字对。
