寻找和为定值的两个数

1. 题目描述

    给定一个数组（无序或者有序，两种情况都要考虑），找出和为M的两个数。最多时间复杂度能有多少？

    https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md

2. 数组有序——两端指针扫描法

    数组有序的情况，在时间复杂度上我们就省去了排序的O(NlogN)。

    我们使用两端指针扫描法是比较简单的，时间复杂度为O(N), 空间复杂度为O(1)。如下图所示：

首先我们在数组两端分别放上一个标志：begin, end。

然后，判断它们指向的值之和sum是否等于M，

               如果sum==M, 记录结果！begin, end同时往中间移动一次；

               如果sum<M, end往中间移动一次；

               如果sum>M, begin往中间移动。

直到，begin>end，返回结果~

总共的时间复杂度就是很厉害的O(N), 空间复杂度也只是O(1)。但是注意前提是数组要有序~

程序如下：

#include <iostream>
#include <algorithm>
using namespace std;

void twoSum(int a[],unsigned int length,int sum)
{
    int begin=0;
    int end=length-1;
    while(begin<end)
    {
        long curSum=a[begin]+a[end];
        if(curSum==sum)
        {
            cout<<"两个数为"<<a[begin]<<" "<<a[end]<<endl;
            break;
        }
        else
        {
            if(curSum>sum)
            {
                end--;
            }
            else{
                begin++;
            }
        }
    }
}

int main()
{
    int a[7]={16,28,4,58,7,11,15};
    sort(a,a+7);
    twoSum(a,7,15);
    return 0;
}

如果需要输出满足所有条件的整数对

在上面代码基础上添加：

#include <iostream>
#include <algorithm>
using namespace std;

void twoSum(int a[],unsigned int length,int sum)
{
    int begin=0;
    int end=length-1;
    while(begin<end)
    {
        long curSum=a[begin]+a[end];
        if(curSum==sum)
        {
            //题目要求输出满足条件的一对
            cout<<"两个数为"<<a[begin]<<" "<<a[end]<<endl;
            //如果需要所有满足条件的数对，需要加上下面两条语句
            begin++;
            end--;
            //break;
        }
        else
        {
            if(curSum>sum)
            {
                end--;
            }
            else{
                begin++;
            }
        }
    }
}

int main()
{
    int a[]={16,28,4,58,7,8,11,15};
    int len=sizeof(a)/sizeof(int);
    sort(a,a+len);
    twoSum(a,len,15);
    return 0;
}

3. 数组无序——映射hash表或者数组

    当数组无序的时候，当时我们可以先排序, 然后再使用上面的方法。这是时间复杂度为O(NlogN)，空间复杂度为O(1)。

    或者我们还可以使用映射hash表或者数组，详细来说：

把数组M - a[i]映射到一个hash表或者是一个数组，然后我们就判断原数组和数组M - a[i]时候有元素相等，如果则返回结果。判断相等的方法我们也可以使用两端夹逼方法。

这种方法的时间复杂度为O(N), 空间复杂度为O(N)。

ps：其实在无序的情况，还是映射到hash表比较好，映射到数组也不是很好操作~

#include <iostream>
using namespace std;
const int size=100;

int main()
{
    int hashtable[size];
    for(int i=0;i<size;i++)
        hashtable[i]=0;
    int a[size]={1,2,4,5,7,11,15};
    for(int i=0;i<7;i++)
        hashtable[a[i]]=1;
    int sum=15;
    for(int i=0;i<7;i++)
        if(hashtable[i]&&hashtable[sum-i])
          cout<<"这两个数为"<<i<<" "<<sum-i<<endl;
        else
          cout<<"不存在这样的两个数."<<endl;
    return 0;
}