Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
问题：求数组中，所有和为0 的三个元素。
解题思路：
自己想了一个解法，但是扔上去超时了，然后在网上看到使用双指针的算法，理解后，把这道题解决了。
第一步，对数组排序。
第二步，
分析1：对于元素 S[i] ， 最后的答案可以分为两种，包含 S[i] 的，和不包含 S[i] 的。当包含 S[i] 的情况都找到后，后续就可以不用在考虑 S[i] 。
对于 S[i] ， l = i+1, r = len-1 。若 s[i] + S[l] + S[r] == 0， 则为原问题的一个解。
- 当 S[i] + S[l] > -S[r] 时，则 r--
- 当 S[i] + S[l] < -S[r] 时，则 l++
- 当 S[i] + S[i] = -S[r] 时， 表示是原问题的一个解，则 l++, r--;
第三步，性能优化。同样根据分析1，若 S[i] == S[i+1]，可以跳过。
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
std::sort(nums.begin(), nums.end());
map<string, vector<int>> key_res;
for (int i = ; i < (int)nums.size(); i++) {
// star 剪枝优化
if (i >= ) {
while (nums[i] == nums[i-]) {
i++;
continue;
}
}
// end 剪枝优化
int l = i+;
int r = (int)nums.size()-;
while (l < r) {
if (nums[l] + nums[r] > -nums[i]) {
r--;
continue;
}
else if (nums[l] + nums[r] < -nums[i]){
l++;
}else{
string k = to_string(nums[i]) + "," + to_string(nums[l]) + "," + to_string(nums[r]);
vector<int> tmp = {nums[i], nums[l] , nums[r]};
key_res[k] = tmp;
l++;
r--;
}
}
}
map<string, vector<int>>::iterator m_iter;
for (m_iter = key_res.begin(); m_iter != key_res.end(); m_iter++) {
res.push_back(m_iter->second);
}
return res;
}