[C国演义] 第十三章

三数之和

力扣链接

根据题目要求:

1. 返回的数对应的下标各不相同
2. 三个数之和等于0
3. 不可包含重复的三元组 – – 即顺序是不做要求的
   如: [-1 0 1] 和 [0, 1, -1] 是同一个三元组
4. 输出答案顺序不做要求

暴力解法: 排序 + 3个for循环 + 去重 — — N^3, 肯定超时
优化: 排序 + 双指针 + 去重 — — N^2
优化的具体思路:
固定一个数, 记作a; 在剩余的空间里面找和为 -a的两个数(由于是排好序的, 所以使用双指针)
去重有两种方法:
1.set去重
2 在循环内部缩小空间 — — 非常值得我们去尝试

1. 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;}
};

上面的运行结果太慢了, 我们尝试一下 缩小空间去重👇👇👇

2. 缩小空间去重

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 和 rightwhile(left < right && nums[left] == nums[left-1])  left++;while(right > left && nums[right] == nums[right+1])  right--;}}// 去重ii++;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 和 rightwhile(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;}
};

---

号令风霆迅，天声动北陬。
长驱渡河洛，直捣向燕幽。
马蹀阏氏血，旗袅可汗头。
归来报明主，恢复旧神州。 — — [宋] 岳飞 <送紫岩张先生北伐>