快速寻找满足条件的两个数

Myth丶恋晨 2022-08-27 15:37 184阅读 0赞

时间：2014.07.17

地点：基地

\-------------------------------------------------------------------------------------

# 一、问题描述 #

给定一个数组，要求快速查找出其中的两个值，他们的和为一个给定的值。

比如给定数组：1 4 5 6 8 9，和给定值9，我们能找出4+5=9为所要的数值

\-------------------------------------------------------------------------------------

# 二、各种解法 #

## 2.1穷举法 ##

对给定集合从中取出任意值求和，看是否等于给定和值，显然由组合公式知：其复杂度为N(N-1)/2，即O(N^2)。我们要求尽可能降低算法时间复杂度和算法空间复杂度，这个算法比较原始。

## 2.2先排序后查找 ##

假定给定数字和为sum，对数组中的每个数字arr\[i\]，理想上是要有另外一个数字sum-arr\[i\]存在数组中即为查找成功，于是问题转换成了一个查找问题，而我们知道查找算法中最快的莫过于二分查找，时间复杂度为O(logN)，但二分查找的前提是有序序列，于是我们要先对数组进行排序，我们也知道快排、堆排、归排等都是时间复杂度为O(NlogN)的排序算法，于是针对数组中的每个数arr\[i\]，都需要花费O(logN)的时间去查找对应的sum-arr\[i\]是否存在，于是总的时间复杂度为O(NlogN)，在这里我们排序也需耗时O(NlogN)，但好在排序只需一次，于是时间复杂度依旧还是O(NlogN)。

使用二分查找时要注意：

1.将数组划分为两个子部分时，中间分界为：

middle=first+size/2

2.左边子部分可能略多，从first开始，大小为size/2

3.右边子部分可能略少，从middle+1开始，大小为(size-1)/2

## 2.3使用哈希查找 ##

在2.2节，我们已经将问题转换成了查找问题，事实上，对于查找问题，若不惜代价追求速度的话，哈希查找最快，每次查找时间复杂度为O(1)，于是在这里我们只需O(N)即可完成任务。此种方法需要增加额外的存储空间。

## 2.4双端扫描 ##

首先若数组无序，排序还是要排，时间复杂度为O(NlogN)，但若数组有序，则可直接O(N)完成任务，在这里我们假设数组是有序的，现在才用双指针双端扫描法对整个数组扫描的策略：  
首先，设定两个指针begin 和 end，分别指向数组首和尾，

然后,逐次判断arr\[\*begin\]+arr\[\*end\]和给定的sum进行大小比较

i.若大于，说明两数和过大，执行--end，缩减两数和

ii.若小于，说明两数和过小，执行++begin，放大两数和

iii.若等于，正是我们所要，返回这个数值对

双端扫描的代码如下：

pair FindSumPair(int* arr, int n, int sum)
    {
    	//Sort(arr,arr+n);               //若数组无序，则先对数组进行排序
    	int* begin = arr;
    	int* end = arr + n - 1;
    	int tem_sum = 0;
    	while (begin < end)
    	{
    		tem_sum = (*begin) + (*end);
    		if (tem_sum>sum)
    			--end;
    		else if (tem_sum < sum)
    			++begin;
    		else
    			return pair(*begin, *end);
    	}
    	return pair(-1, -1);
    }

\-------------------------------------------------------------------------------------

# 三、扩展 #

2010年中兴面试题-编程求解：  
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,  
使其和等于 m, 要求将其中所有的可能组合列出来。

引用算法之道JULY博客中的代码如下：

#include<list>  
    #include<iostream>  
    using namespace std;  
      
    list<int>list1;  
    void find_factor(int sum, int n)   
    {  
        // 递归出口  
        if(n <= 0 || sum <= 0)  
            return;  
          
        // 输出找到的结果  
        if(sum == n)  
        {  
            // 反转list  
            list1.reverse();  
            for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)  
                cout << *iter << " + ";  
            cout << n << endl;  
            list1.reverse();      
        }  
          
        list1.push_front(n);      //典型的01背包问题  
        find_factor(sum-n, n-1);   //放n，n-1个数填满sum-n  
        list1.pop_front();  
        find_factor(sum, n-1);     //不放n，n-1个数填满sum   
    }  
      
    int main()  
    {  
        int sum, n;  
        cout << "请输入你要等于多少的数值sum:" << endl;  
        cin >> sum;  
        cout << "请输入你要从1.....n数列中取值的n：" << endl;  
        cin >> n;  
        cout << "所有可能的序列，如下：" << endl;  
        find_factor(sum,n);  
        return 0;  
    }