蓝桥杯算法竞赛系列第十章·nSum问题的代码框架

首先，何为nSum问题呢？

nSum问题其实就是给你一个数组nums和一个目标和target，让我们从nums数组中选择n个数，使得这些数字之和等于target。

由此衍生出了两数之和，三数之和，四数之和……

今天可借用一个算法框架，求解100Sum也不不在话下！

一、两数之和

题目链接：两数之和II-输入有序数组

题目要求：

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

简单来说就是：

给我们一个数组和一个目标值，让我们找到和为目标值的两个数的下标。

看起来好像很简单，雀实不难。

解题思路：

首先对数组进行排序，因为本题已经是有序的了，所以不同排序了（手动狗头）

然后就是定义双指针，一个在前一个在后，比较两数之和，就行了。

代码详解：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) 
    {
        // 定义前后指针
        int left = 0, right = numbers.size() - 1;

        while(left < right)
        {
            // 前后两个数之和
            int sum = numbers[left] + numbers[right];
						// 根据 sum 和 target 的比较，移动左右指针
            if(sum < target)
            {
                left++;
            }
            else if (sum > target)
            {
                right--;
            }
            else if(sum == target)
            {
                return {left + 1, right + 1};
            }
        }

        return {-1, -1};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

变形题

下面这这道题进行变形，变得更困难一点：

nums 中可能有多对儿元素之和都等于 target，请你的算法返回所有和为 target 的元素对儿，其中不能出现重复。

还数签名如下：

vector<vector<int>> twoSumTarget(vector<int>& nums, int target);
1

对于这个修改后的问题，关键难点在于现在可能有多个和为target 的数对，还不能重复，比如[1, 3]和[3, 1]就是重复的。

首先解题思想肯定还是和上面一样：排序 + 双指针

while (lo < hi) 
{
    int sum = nums[lo] + nums[hi];
    // 记录索引 lo 和 hi 最初对应的值
    int left = nums[lo], right = nums[hi];
    if (sum < target)      
      	lo++;
    else if (sum > target)
      	hi--;
    else if (sum == target) 
    {
      	// 解题的关键就在于sum == target的情况，这里前后指针需要跳过所有重复的元素
        res.push_back({left, right});
        // 跳过所有重复的元素
        while (lo < hi && nums[lo] == left) lo++;
        while (lo < hi && nums[hi] == right) hi--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

OK，到这里，一个通用的twoSum函数就算是写出来了，注意理解哦，因为整个nSum问题都会用到这个函数。

二、三数之和

题目链接：三数之和

解题思路：

题目要求我们在数组nums中找到和为0的三个数，也就是说这里的n是3，target是0

其实说到底还是穷举，现在要求我们找到和为target的三个数，对于第一个数来说，nums数组中的所有数字都可能是，但是只要第一个数字确定了，剩下的两个数可以是什么呢 ？其实也就是和为target - nums[i]的两个数，这样一来，又回到了twoSum问题本身。

OK，请看下面代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        // 先对数组进行排序
        sort(nums.begin(), nums.end());
        
        // 为了更好的复用，直接封装成为nSum函数
        return nSum(nums, 3, 0, 0);
    }

    vector<vector<int>> nSum(vector<int>& nums, int n, int start, int target)
    {
        int sz = nums.size();

        vector<vector<int>> res;

        // 注意边界
        if(n < 2 || n > sz)
        {
            return res;
        }

        if(n == 2)
        {
            // 其实就是twoSum代码框架
            int left = start, right = sz - 1;

            while(left < right)
            {
                int leftNum = nums[left], rightNum = nums[right];
                int sum = leftNum + rightNum;

                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});

                    while(left < right && leftNum == nums[left])
                        left++;
                    while(left < right && rightNum == nums[right])
                        right--;
                }
            }
        }
        else
        {
            // n > 2的情况，递归计算(n-1)Sum的结果
            for(int i = start; i < sz; i++)
            {
                // 也就是说，计算三数之和，先递归计算两数之和
                vector<vector<int>> twoNums = nSum(nums, n - 1, i + 1, target - nums[i]);

                // 将两数之和的结果加上当前的元素就是题目所求的三数之和
                for(auto twoNum : twoNums)  
                {
                    // (n-1)Sum 加上 nums[i] 就是 nSum
                    twoNum.push_back(nums[i]);
                    res.push_back(twoNum);
                }

                // 防止第一个元素重复
                while(i < sz - 1 && nums[i] == nums[i + 1])
                {
                    i++;
                }
            }
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

代码虽然看起来比较长，但是只要理解了就很简单，因为n==2时就是twoSum的双指针解法，n > 2时就是穷举第一个数字，然后递归计算(n-1)Sum，组长答案。

还有一点需要注意的是，类似 twoSum，3Sum 的结果也可能重复，比如输入是 nums = [1,1,1,2,3], target = 6，结果就会重复。

关键点在于，不能让第一个数重复，至于后面的两个数，我们复用的 twoSum 函数会保证它们不重复。所以代码中必须用一个 while 循环来保证 nSum 中第一个元素不重复。

三、四数之和

原题链接：四数之和

解题思路：

没啥好说的了，理解了上面的三数之和这道题自然就没有问题。

只有一点需要注意，就是target类型需要定义为long long 防止溢出。因为这道题说了 nums[i] 和 target 的取值都是 [-10^9, 10^9]，int 类型的话会造成溢出。

代码详解：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        // 先对数组进行排序
        sort(nums.begin(), nums.end());

        return nSum(nums, 4, 0, target);
    }

    vector<vector<int>> nSum(vector<int>& nums, int n, int start, long target)
    {
        int sz = nums.size();

        vector<vector<int>> res;

        if(n < 2 || n > sz)
            return res;

        if(n == 2)
        {
            int left = start, right = sz - 1;

            while(left < right)
            {
                int leftNum = nums[left], rightNum = nums[right];
                int sum = leftNum + rightNum;

                if(sum < target)
                {
                    left++;
                }
                else if(sum > target)
                {
                    right--;
                }
                else if(sum == target)
                {
                    res.push_back({leftNum, rightNum});

                    while(left < right && leftNum == nums[left])
                        left++;
                    while(left < right && rightNum == nums[right])
                        right--;
                }
            }
        }
        else
        {
            // n > 2
            for(int i = start; i < sz; i++)
            {
                vector<vector<int>> threeNums = nSum(nums, n - 1, i + 1, target - nums[i]);

                for(auto threeNum : threeNums)
                {
                    threeNum.push_back(nums[i]);
                    res.push_back(threeNum);
                }

                // 防止第一个元素重复
                while(i < sz - 1 && nums[i] == nums[i + 1])
                {
                    i++;
                }
            }
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71