蓝桥杯算法竞赛系列第十章·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};}
};

变形题

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

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

还数签名如下：

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

对于这个修改后的问题，关键难点在于现在可能有多个和为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--;}
}

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] 就是 nSumtwoNum.push_back(nums[i]);res.push_back(twoNum);}// 防止第一个元素重复while(i < sz - 1 && nums[i] == nums[i + 1]){i++;}}}return res;}
};

代码虽然看起来比较长，但是只要理解了就很简单，因为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 > 2for(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;}
};

蓝桥杯算法竞赛系列第十章·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};}
};

变形题

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

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

还数签名如下：

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

对于这个修改后的问题，关键难点在于现在可能有多个和为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--;}
}

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] 就是 nSumtwoNum.push_back(nums[i]);res.push_back(twoNum);}// 防止第一个元素重复while(i < sz - 1 && nums[i] == nums[i + 1]){i++;}}}return res;}
};

代码虽然看起来比较长，但是只要理解了就很简单，因为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 > 2for(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;}
};