三数之和
根据题目要求:
返回的数对应的下标各不相同
三个数之和等于0
不可包含重复的三元组 – – 即顺序是不做要求的
如: [-1 0 1] 和 [0, 1, -1] 是同一个三元组
输出答案顺序不做要求
暴力解法: 排序 + 3个for循环 + 去重 — — N^3, 肯定超时
优化: 排序 + 双指针 + 去重 — — N^2
优化的具体思路:
固定一个数, 记作a; 在剩余的空间里面找和为 -a的两个数(由于是排好序的, 所以使用双指针)
去重有两种方法:
1.set去重
2 在循环内部缩小空间 — — 非常值得我们去尝试
set去重
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { // 排序 sort(nums.begin(), nums.end()); // 记录结果 vector<vector<int>> res; // 固定一个数 + 双指针 int n = nums.size(); for(int i = 0; i < n; i++) // 固定一个数 { // 双指针优化 int left = i+1, right = n-1; int targt = -nums[i]; while(left < right) { int sum = nums[left] + nums[right]; if(sum < targt) { left++; } else if(sum > targt) { right--; } else { res.push_back({nums[i], nums[left], nums[right]}); left++; right--; } } } // 去重 set<vector<int>> result(res.begin(), res.end()); res.clear(); for(auto e : result) { res.push_back(e); } return res; } };
上面的运行结果太慢了, 我们尝试一下 缩小空间去重👇👇👇
- 缩小空间去重
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { // 排序 sort(nums.begin(), nums.end()); // 记录结果 vector<vector<int>> res; // 固定一个数 + 双指针 int n = nums.size(); for(int i = 0; i < n;) // 固定一个数 { // 双指针优化 int left = i+1, right = n-1; int targt = -nums[i]; while(left < right) { int sum = nums[left] + nums[right]; if(sum < targt) { left++; } else if(sum > targt) { right--; } else { res.push_back({nums[i], nums[left], nums[right]}); left++; right--; // 去重left 和 right while(left < right && nums[left] == nums[left-1]) left++; while(right > left && nums[right] == nums[right+1]) right--; } } // 去重i i++; while(i < n && nums[i] == nums[i-1]) i++; } return res; } };
四数之和
这一题就跟上面的题目相似, 思路也很相似: 排序 + 固定两个数, 双指针优化 + 去重. 当然, 我们这里的去重逻辑也是 缩小空间去重
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int n = nums.size(); // 选定一个数, 内部用三数之和 for(int i = 0; i < n;) { // 选定一个数, 内部使用双指针优化 for(int j = i+1; j < n;) { int left = j+1, right = n-1; long int tar = target - (long int)(nums[i]+nums[j]); while(left < right) { long int cur = nums[left] + nums[right]; if(cur < tar) left++; else if(cur > tar) right--; else { res.push_back({nums[i], nums[j], nums[left], nums[right]}); left++, right--; // 去重left 和 right while(left < right && nums[left] == nums[left-1]) left++; while(right > left && nums[right] == nums[right+1]) right--; } } // j的去重 j++; while(j < n && nums[j] == nums[j-1]) j++; } // i的去重 i++; while(i < n && nums[i] == nums[i-1]) i++; } return res; } };
