n sum

问题：

　　给定一个TargetNumber和一个Array，在Array中找出n个数，这n个数之和等于TargetNumber。

分析：

　　当n==1时，此时变成了典型的一维数组查找问题，可以采用排序和二分查找的方法。

　　当n==2时，先按升序排序，ptr1指向数组头，ptr2指向数组尾。若指针所指2数之和大于TargetNumber时，ptr2向队首移动一位，若指针所指的2数之和小于　　　　　TargetNumber时，ptr1向队尾移动一位。当2数之和与TargetNumber相等时，2个指针所指的数即为结果。

　　当n==3时，首先对数组进行排序，定义三个位置ptr1、ptr2、ptr3指向三个位置。初始化ptr1指向队首，并固定ptr1的位置，对ptr2和ptr3使用类似TwoSum的　　　　策略进行搜索，为了提升搜索运行效率，可以在搜索前通过边界判断，缩小搜索范围。ptr2和ptr3相遇后，向后移动ptr1，重新给ptr2和ptr3赋值，再次执　　　　行TwoSum的搜索策略。

代码：ThreeSum

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<vector<int>> findThreeSum(vector<int> nums, int target)
{
    vector<vector<int>> ret;
    int n = nums.size();
    if(n < 3)
        return ret;
    
    sort(nums.begin(), nums.end());
    
    for(int ptr1 = 0; ptr1 < n - 2; ptr1++)
    {
        int ptr2 = ptr1 + 1;
        int ptr3 = n - 1;
        if(nums[ptr1] + nums[ptr1 + 1] + nums[ptr1 + 2] > target)
            break;
        if(nums[ptr1] + nums[n - 1] + nums[n - 2] < target)
            continue;
        
        while(ptr2 < ptr3)
        {
            int sum = nums[ptr1] + nums[ptr2] + nums[ptr3];
            if(sum == target)
            {
                vector<int> tmp = {nums[ptr1], nums[ptr2], nums[ptr3]};
                ret.push_back(tmp);
                ptr2++;
                ptr3--;
            }
            else if(sum < target)
                ptr2++;
            else
                ptr3--;
        }
    }
    
    return ret;
}

int main()
{
    vector<int> num = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    vector<vector<int>> ret = findThreeSum(num, 20);
    
    for(auto x : ret)
    {
        std::cout << "items : ";
        for(auto y : x)
        {
            std::cout << y << " ";
        }
        std::cout << std::endl;
    }
    
    return 0;
}

运行结果：

 

 n sum需要用回溯加剪枝的方式。