Leetcode刷题 ——N Sum问题总结

2Sum

（https://leetcode.com/problems/two-sum/） 详细题解：https://www.acwing.com/solution/LeetCode/content/47/

题目描述 给定一个整型数组，要求返回两个数的**下标**，使得两数之和等于给定的目标值，要求同一个下标不能使用两次。 数据保证有且仅有一组解。 样例 给定数组 nums = [2, 7, 11, 15]，以及目标值 target = 9， 原始思路： 用两个for循环遍历数组，找出结果，时间复杂度为O(n2) //优化思路1：（这里需要返回下标，此思路不好） //排序后双指针做，时间复杂度为O(nlogn) 优化思路2： 使用hash表，建立HashMap<Integer, Integer> map，键值对为<nums[i]，i>。遍历数组nums，对每个数nums[i]，查询hash表中是否有key等于target-nums[i]的记录，若有，则找到；否则，将num[i]和下标i存入hash表。因为hash表的查找时间复杂度可以看作是O(1)，所以算法时间复杂度就降为O(n)了.

代码：

vector<int> twoSum(vector<int>& nums, int target) { vector<int> res; int len = nums.size(); if (!len) return res; unordered_map<int, int> hash; for (int i = 0; i < len; i++){ if (hash.find(target - nums[i]) != hash.end()){ return vector<int>({hash[target-nums[i]], i}); } hash[nums[i]] = i; } return res; }

3Sum

（https://leetcode.com/problems/3sum/） 详细题解：https://www.acwing.com/solution/LeetCode/content/60/

题目描述 类似于Two Sum，给定一个整型数组，要求返回所有不重复的三元组，且每个三元组的和等于0。 样例 给定数组 nums = [-1, 0, 1, 2, -1, -4]，返回 [ [-1, 0, 1], [-1, -1, 2] ]。 原始思路： 3个for循环，但会超时 优化思路： 使用双指针，首先将数组排序（防止重复），然后一重循环**无重复**枚举第一个数字，然后接下来采用 两头向里寻找的方式无重复的构造剩下的两个数字，具体在循环中： 1. 初始化l为st+1，r为n-1。 2. 当l<r时，如果当前nums[l] + nums[r] + nums[i]== target，则增加答案并同时向后**无重复移动**l，向前**无重复移动**r； 否则根据nums[l] + nums[r]+ nums[i]与target的关系判断移动l还是移动r。这种方法的时间复杂度可以控制在O(n2)。

代码：

vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> res; if (nums.size() < 3) return res; sort(nums.begin(), nums.end()); int len = nums.size(); for (int i = 0; i < len; i++){ while(i && i < len && nums[i] == nums[i - 1]) i++; // 无重复地枚举每一个数字 + 判边界 int l = i + 1, r = len - 1; while(l < r){ if (nums[l] + nums[r] + nums[i] == 0){ res.push_back(vector<int>({nums[i], nums[l], nums[r]})); while(l < r && nums[l + 1] == nums[l]) l++; // 无重复地移动 while(l < r && nums[r - 1] == nums[r]) r--; // 无重复地移动 l++; r--; } else if (nums[l] + nums[r] + nums[i] > 0) r--; else l++; } } return res; }

3Sum Closet

（https://leetcode.com/problems/3sum-closest/） 详细题解： https://www.acwing.com/solution/LeetCode/content/64/

题目描述 给定一个整型数组和一个目标值target，要求从数组中选出三个数使得它们的和与target最接近，返回这个和。数据保证仅有一个最优解。 样例 给定数组 nums = [-1, 2, 1, -4]，以及目标值 target = 1。 由于 nums[0] + nums[1] + nums[2] = -1 + 2 + 1 = 2，与 target 最接近，所以返回 2。 原始思路： 3个for循环，但会超时 优化思路： 使用双指针，首先将数组排序（防止重复），然后一重循环**无重复**枚举第一个数字，然后接下来采用 两头向里寻找的方式无重复的构造剩下的两个数字，具体在循环中： 1. 初始化l为**st+1**，r为n-1。 2. 当l<r时，如果当前nums[l] + nums[r] + nums[i]== target，直接返回答案target。 否则根据nums[l] + nums[r]与target的关系判断移动l还是移动r。这种方法的时间复杂度可以控制在O(n2)。

代码：

int threeSumClosest(vector<int>& nums, int target) { if (nums.size() < 3) return 0; int len = nums.size(); sort(nums.begin(), nums.end()); int sum = nums[0] + nums[1] + nums[2]; // 选0会Bug,选INT_MAX或INT_MIN有溢出风险 for (int i = 0; i < len; i++){ while(i && i < len && nums[i] == nums[i - 1]) i++; int l = i + 1, r = len - 1; while(l < r){ int tmp = nums[l] + nums[r] + nums[i]; if (tmp == target) return target; else if (tmp > target) r--; else l++; if (abs(target - tmp) < abs(target - sum)) sum = tmp; } } return sum; }

4Sum

（https://leetcode.com/problems/4sum/） 详细题解: https://www.acwing.com/solution/LeetCode/content/66/

题目描述 类似于 3Sum，给定一个整型数组和 targettarget，要求返回所有不重复的四元组，且每个四元组的和等于 target。 样例 给定数组 nums = [1, 0, -1, 0, -2, 2] 和 target = 0 返回 [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]。 原始思路： 4重枚举，超时 优化思路： 首先将数组排序（防止重复），然后2重**无重复**枚举第一个数字和第二个数字。接下来采用两头向里寻找的方式无重复的构造剩下的两个数字，具体在循环中： 1. 初始化l为**st+1**，r为n-1。 2. 当l<r时，如果当前nums[l] + nums[r] + nums[i] + nums[j] == target，直接返回答案target。 否则根据nums[l] + nums[r] + nums[i] + nums[j]]与target的关系判断移动l还是移动r。这种方法的时间复杂度可以控制在O(n2)。 特别注意： 如何做到**无重复**枚举，详见代码。范围设置很重要

代码:

vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> res; if (nums.size() < 4) return res; int len = nums.size(); sort(nums.begin(), nums.end()); for (int i = 0; i < len; i++){ while(i && i < len && nums[i] ==nums[i - 1]) i++; // 无重复枚举 for (int j = i + 1; j < len; j++){ while(j > i + 1 && j < len && nums[j] == nums[j - 1]) j++; // 无重复枚举 int l = j + 1, r = len - 1; while(l < r){ int tmp = nums[i] + nums[j] + nums[l] + nums[r]; if (tmp == target){ res.push_back(vector<int>({nums[i], nums[j], nums[l], nums[r]})); while(l < r && nums[l + 1] == nums[l]) l++; while(l < r && nums[r - 1] == nums[r]) r--; l++; r--; } else if (tmp > target) r--; else l++; } } } return res; }

4Sum II （https://leetcode.com/problems/4sum-ii/submissions/） 详细题解：https://www.acwing.com/solution/LeetCode/content/358/

题目描述 给定四个整型数组 A、B、C和D，计算有多少四元组 (i, j, k, l) 使得 A[i] + B[j] + C[k] + D[l] 等于0。 为了使问题简单一些，A、B、C和D长度相同且为N，0≤N≤5000≤N≤500。所有的整数在−228−228到228−1228−1内，答案个数保证不超过231−1231−1。 样例 Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 解释: 两个四元组为： 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 原始思路： 4重循环，超时 优化思路： 先两重循环。将中间答案用哈希表记录。然后再循环剩下两个数组，看他们的相反数是否已经存在在hash 表中，如果存在，则将对应的次数累加到答案中。

代码：

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { int res = 0; int len = A.size(); unordered_map<int, int> hash; for (int i = 0; i < len; i++){ for (int j = 0; j < len; j++){ hash[A[i] + B[j]] ++; } } for (int i = 0; i < len; i++){ for (int j = 0; j < len; j++){ if (hash.find(-C[i] - D[j]) != hash.end()) res += hash[-C[i] - D[j]]; } } return res; }