给定一个整型数组，数组未排序，请找出一对数，使这两个数的和等于一个给定的值。
例如，
输入:
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)

1. 傻瓜式方法

傻瓜式方法比较粗暴，通过遍历给定数组中的所有两个数字组成的组合，只要发现一个组合的和等于期望中的数字，就返回它们。

C语言实现：

#include

// 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; } [/c] 下载代码 运行代码

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); } } [/java] 下载代码 运行代码

输出：
Pair found at index 0 and 2

这种解决方案的时间复杂度是 O(n²)，空间复杂度是 O(1)。

2. 使用排序复杂度为O(nlogn)的方法

这种方法的观点是，先对数组进行排序，然后通过两个索引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

// 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; } [/cpp] 下载代码 运行代码

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); } } [/java] 下载代码 运行代码

输出:
Pair found

这种解决方案的时间复杂度是 O(nlogn)，空间复杂度是 O(1)。

3. 使用Map复杂度为O(n)的方法

其实，我们可以在线性的时间内解决问题，解决方案的关键在于使用map。算法就是把数组中的元素arr[i]插入到map中。在遍历数组过程中，我们需要查找sum – arr[i]是否在数组中。如果能找到，就打印出arr[i]和sum-array[i]，返回。

C++语言实现：

#include
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 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; } [/cpp] 下载代码 运行代码

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 map = new HashMap();

// 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); } } [/java] 下载代码 运行代码

输出：
Pair found at index 0 and 2

这种方案的时间复杂度和空间复杂度都是O(n)。

练习： 打印出数组中所有和等于给定值的数字对。

|      2017年05月05日 星期五  22:13:21| 算法设计| 添加评论|