找出数组中满足给定和的元素

3.找出两个数组中满足给定和的数对，如果数组没序，先排序

问题描述：有两个数组arr1和arr2，两个数组均已经排好序，现在要找出这样的x和y使得x+y=sum，其中sum已知，x是arr1中某个元素，y是arr2中的某个元素。

解决方案：既然数组arr1和arr2中的元素已经排好序了，那么问题就简单了不少。假设arr1[i] + arr2[j] > sum，若arr1下标不变，那么要找到满足条件的x和y，只能取arr2中下标< j 的元素和arr1[i]相加，结果才可能等于sum；假设arr1[i] + arr2[j] < sum，若arr2的下标不变，那么要找到满足条件的x和y，只能取arr1中下标 > i 的元素和arr2[j]相加，结果才可能等于sum。因此我们可以设置两个指针 i 和 j ，分别指向arr1的开始位置和结束位置，这时 i 只能不断变大，j 只能不断变小，直到超过了数组的范围。通过代码更好理解，看代码吧~~时间复杂度是O(n+m)，n和m分别是arr1和arr2的大小。

#include

//这里是两个有序数组，找出数组中两个数的和是固定值
//其实跟一个有序数组找给定和也差不多
void fin2m(int *a,int m,int *b,int n,int x)
{
    int i=0,j=n-1;
    while(i=0)
    {
        if(a[i]+b[j]>x)
            j--;
        else if(a[i]+b[j]
            i++;
        else
        {
            printf("the two: %d %d\n",a[i],b[j]);
            i++;
            j--;
        }
    }
}
int main()
{
    int a[10]={1,4,6,8,9,13,15,16,18,20};
    int b[11]={11,14,16,18,19,23,25,26,28,30,31};
    fin2m(a,10,b,11,22);
    return 0;
}

/*
the two: 4 18
the two: 6 16
the two: 8 14
Press any key to continue
*/

其实这题，可扩展为在一个有序数组中，找出满足给定和的数对
总结：

• 不论原序列是有序还是无序，解决这类题有以下三种办法：1、二分（若无序，先排序后二分），时间复杂度总为O（n*logn），空间复杂度为O（1）；2、扫描一遍X-S[i]  映射到一个数组或构造hash表，时间复杂度为O（n），空间复杂度为O（n）；3、两个指针两端扫描（若无序，先排序后扫描），时间复杂度最后为：有序O（n），无序O（n*logn+n）=O（n*logn），空间复杂度都为O（1）。
• 所以，要想达到时间O（N），空间O（1）的目标，除非原数组是有序的（指针扫描法），不然，当数组无序的话，就只能先排序，后指针扫描法或二分（时间n*logn，空间O（1）），或映射或hash（时间O（n），空间O（n））。时间或空间，必须牺牲一个，自个权衡吧。
• 综上，若是数组有序的情况下，优先考虑两个指针两端扫描法，以达到最佳的时（O（N）），空（O（1））效应。否则，如果要排序的话，时间复杂度最快当然是只能达到N*logN，空间O（1）则是不在话下。

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

求解思路：每个数都有两种选择，加入与不加入 实际上就是一个背包问题，可用回溯法求解

1.首先判断，如果n>m，则n中大于m的数不可能参与组合，此时置n = m;

2.将最大数n加入且n == m,则满足条件，输出；

3.将n分两种情况求解，（1）n没有加入，取n = n - 1; m = m;递归下去；（2）n加入，取n = n - 1l, m = m - n,递归下去

#include
#include
using namespace std;

listlist1;//相当于栈，不过出入比栈效率高
void find_factor(int sum, int n)
{
    // 递归出口
    if(n <= 0 || sum <= 0)
        return;

    // 输出找到的结果
    if(sum == n)
    {
        for(list::iterator iter = list1.begin(); iter != list1.end(); iter++)
            cout << *iter << " + ";
        cout << n << endl;//n不在栈里面的，这里的实现有点技巧
    }

    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;
}

/*
请输入你要等于多少的数值sum:
10
请输入你要从1.....n数列中取值的n：
6
所有可能的序列，如下：
6 + 4
3 + 6 + 1
4 + 5 + 1
3 + 5 + 2
2 + 3 + 4 + 1
Press any key to continue
*/