題目描述
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: 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]
]
給定一個(gè)有n個(gè)整數(shù)的數(shù)組S, 判斷是否存在a, b, c三個(gè)元素滿足a + b + c = 0? 找到數(shù)組中所有滿足和為零的三個(gè)數(shù)（數(shù)組中不能有重復(fù)的三個(gè)數(shù)） 差导。
代碼及注釋
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 最終結(jié)果可能是多個(gè)vector
vector<vector<int>> result;
// 數(shù)組長(zhǎng)度小于3口四，無(wú)結(jié)果
if(nums.size()<3) return result;
// 先對(duì)數(shù)組進(jìn)行排序
sort(nums.begin(),nums.end());
// 可修改target，使3sum最終結(jié)果為多少
const int target = 0;
// last是個(gè)迭代器蜒谤，賦予auto類(lèi)型
auto last = nums.end();
// i指針最外層循環(huán)
for(auto i = nums.begin();i<last-2;++i){
// 內(nèi)部循環(huán)初始j指針是i后面一個(gè)
auto j = i+1;
// 當(dāng)i變化時(shí)氮帐，如果重復(fù)則跳過(guò)昆庇。
if(i>nums.begin() && *i == *(i-1)) continue;
// 內(nèi)部循環(huán)初始k是最后一個(gè)位置
auto k = last-1;
// 停止條件j<k
while(j<k){
if(*i + *j + *k <target){
++j;
// 指針每次變化都需要檢驗(yàn)是否重復(fù)
while(*j == *(j-1) && j<k) ++j;
}
else{
if(*i + *j + *k > target){
--k;
while(*k == *(k+1) && j<k) --k;
}
else{
result.push_back({*i,*j,*k});
++j;
--k;
while(*j == *(j-1) && *k == *(k+1) && j<k) ++j;
}
}
}
}
return result;
}
};
分析
假定滿足條件的三個(gè)數(shù)為a,b,c榄棵，這三個(gè)數(shù)索引分別為i, j, k嘲更。
先排序筐钟，
從數(shù)組的頭確定一個(gè)數(shù)a，b的索引比a大1赋朦，c為數(shù)組的尾篓冲，有三種情況
a + b + c = target 則i++ k-- 并把這三個(gè)數(shù)記錄下來(lái)
a + b + c < target 說(shuō)明選的值還太小，j增大微調(diào)宠哄，則j++
a + b + c > target 說(shuō)明選的值太大壹将，k減小調(diào)整，則k--
終止條件b < c毛嫉。
相當(dāng)于確定兩個(gè)诽俯，動(dòng)一個(gè)
