今天，带来哈希相关算法的讲解。文中不足错漏之处望请斧正！
理论基础点这里
三数之和
分析题意
这就是三数之和去重版嘛。
题意转化
求三元组, 满足每个元素相加为0，其中每个元素下标不同；而得到的三元组不能重复。
- 构成三元组的三个元素下标不同
- 三元组和三元组之间不同
怎么理解“三元组和三元组之间不同”：[-1, 0, 1]和[-1, 0, 1]是相同的，尽管构成这两个三元组的元素不同， 但它俩是相同的。
解决思路
1. 哈希法
这道题如果用哈希法，和之前差别不大：两层for遍历nums，一层取a，一层取b，求和映射到哈希表。然后再遍历nums，看看是否有(0-(a+b))这样的元素。
但是这道题用哈希法是比较复杂的，因为去重操作比较麻烦。
2. 双指针法
大概的思路是这样：
- 排序
- 给三个指针
- i，用for控制，固定往后走，取a
- left，初始化为i后面的元素，取b
- right，是最后一个元素，取c
- 当
nums[i] + nums[left] + nums[right] > 0：三个数的和太大了，我们需要让某个数变小，所以--right - 当
nums[i] + nums[left] + nums[right] < 0：三个数的和太小了，我们需要让某个数变大，所以++left - 当
nums[i] + nums[left] + nums[right] == 0：收集结果
再简单点说：
- 排序
- i固定取a
- 固定了a后，移动left和right取b和c，收割符合条件的结果集
排序带来的有序性让我们拿取元素的时候做到有的放矢。
怎么去重？
对三元组去重，只需要保证我们每次取完结果集后，把已经取过的结果集跳过就行。或者说，只要保证所有三元组的第一、二、三个元素的值不等就行。
首先，a的去重：排序后的nums，只要a不和相邻元素相等，就不是重复的。
下面两种选哪种呢？
if(nums[i] == nums[i + 1]) continue;if(nums[i] == nums[i - 1]) continue;
这不是一样的吗？不一样：第一种是判断num[i]和它后面的一个元素是否相等，但这有可能会把某个结果给去掉了。比如[-1, -1, 2]，这是符合条件的结果集，但是当i=0，你判断nums[i] == nums[i + 1](-1 == -1)，就直接跳过了，不对。
简单理解，如果有一个结果集是[-1, b, c]，那往后就不能再出现其他三元组是以[-1]开头的。
其次，b和c的去重。看这个例子：
[0, -1, -1, -1, 1, 1, 1]，这个例子只有一个结果集：[0, -1, 0]当我们收获了第一个结果集[0, -1, 1]后，left和right按理讲都往里面收缩一下。但不一定只是一下，如果只收缩一下，那就可能会重复收割相同的结果集。所以，当left和right收缩后还是重复，就继续收缩，直到不重复。
对a的去重保证：在同一轮循环中不添加相同的三元组。
对bc的去重保证：在整体结果中不添加已经存在的三元组。
编程实现
哈希
class Solution {
public:
// 分析题意: 三数之和 去重版
// 题意转化: 求三元组, 满足每个元素相加为0, 其中每个元素下标不同; 而得到的三元组不能重复(不能完全相同)
// 编程实现
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); ++i) { // 取a
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
unordered_set<int> set; // 固定a, 取所有的b放入set
for (int j = i + 1; j < nums.size(); ++j) {
if (j > i + 2 &&
nums[j] == nums[j - 1] &&
nums[j - 1] == nums[j - 2]) continue; // 对b的去重(相邻元素只取第一次出现的)
int c = 0 - (nums[i] + nums[j]);
if (set.find(c) != set.end()) { // 找c
result.push_back({nums[i], nums[j], c});
set.erase(c); // 对c的去重
} else {
set.insert(nums[j]);
}
}
}
return result;
}
};
双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int i = 0;
int left = 0;
int right = 0;
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (auto &e : nums) cout << e << " ";
cout << endl;
for (i = 0; i < nums.size(); ++i) { // i 取 a
if(nums[i] > 0) return result; //剪枝: 排序后，第一个数(min)都大于0，任何组合都不能等于0了
if (i > 0 && nums[i] == nums[i - 1]) continue; // a的去重
left = i + 1;
right = nums.size() - 1;
// 对于当前a, 不断用left, right 取 b, c, 看看能不能收割结果集
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) --right;
else if (sum < 0) ++left;
else {
while (left < right && nums[left] == nums[left + 1]) ++left; // b的去重
while (left < right && nums[right] == nums[right - 1]) --right; // c的去重
result.push_back({ nums[i], nums[left], nums[right] });
++left;
--right;
}
}
}
return result;
}
};
不对a去重:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int i = 0;
int left = 0;
int right = 0;
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (auto &e : nums) cout << e << " ";
cout << endl;
for (i = 0; i < nums.size(); ++i) { // i 取 a
// if (i > 0 && nums[i] == nums[i - 1]) continue;
left = i + 1;
right = nums.size() - 1;
// 对于当前a, 不断用left, right 取 b, c, 看看能不能收割结果集
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) --right;
else if (sum < 0) ++left;
else {
while (left < right && nums[left] == nums[left + 1]) ++left;
while (left < right && nums[right] == nums[right - 1]) --right;
result.push_back({ nums[i], nums[left], nums[right] });
printf("new result: i=%d left=%d right=%d\n\t\
nums[i]=%d nums[left]=%d nums[right]=%d\n",
i, left, right, nums[i], nums[left], nums[right]);
++left;
--right;
}
}
}
return result;
}
};
不对bc去重:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int i = 0;
int left = 0;
int right = 0;
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (auto &e : nums) cout << e << " ";
cout << endl;
for (i = 0; i < nums.size(); ++i) { // i 取 a
if (i > 0 && nums[i] == nums[i - 1]) continue;
left = i + 1;
right = nums.size() - 1;
// 对于当前a, 不断用left, right 取 b, c, 看看能不能收割结果集
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) --right;
else if (sum < 0) ++left;
else {
// while (left < right && nums[left] == nums[left + 1]) ++left;
// while (left < right && nums[right] == nums[right - 1]) --right;
result.push_back({ nums[i], nums[left], nums[right] });
printf("new result: i=%d left=%d right=%d\n\t\
nums[i]=%d nums[left]=%d nums[right]=%d\n",
i, left, right, nums[i], nums[left], nums[right]);
++left;
--right;
}
}
}
return result;
}
};
今天的分享就到这里了，感谢您能看到这里。
这里是培根的blog，期待与你共同进步！
