題目:
Given an array of n integers, are there elements a, b, c in 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. Example: | 給定一個包含 n 個整數的數組 ,判斷 中是否存在三個元素 a,b,c ,使得 a + b + c = 0 ?找出所有滿足條件且不重複的三元組。 注意:答案中不可以包含重複的三元組。 |
思路:先對原數組排序,然後周遊排序後的數組。在循環内可以做如下優化:1.若目前周遊的 數是正數,就 break;因為目前數組已經是有序,後面的數字肯定是正數,和就不會是0,;2.加上重複跳過功能,,若第2個數與前面數相等則跳過。
我們使target=0-周遊過的數,然後檢視剩下的元素是否為target。我們使用兩個指針,i從目前周遊元素下一個開始從前往後,j從後往前,若兩個數之和剛好為target,将目前元素,i和j一起放入ret,然後兩個指針跳過重複元素。若兩數之和小于target,則左指針向右移動一位,若大于target,j向左移動一位。
注意:1.若vector.size()需要用到兩次以上,最好定義一個變量來儲存vector的size(),這會省時間。
2.不要在循環體内定義變量,這也會造成浪費時間。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ret;
sort(nums.begin(),nums.end());
if(nums.empty()) return {};
int len=nums.size(),i,j,target;
for(int k=0;k<len;++k)
{
if(nums[k]>0) break;
if(k>0 && nums[k]==nums[k-1]) continue;
i=k+1;
j=len-1;
target = 0-nums[k];
while(i<j)
{
if(nums[i]+nums[j]==target)
{
ret.push_back({nums[k],nums[i],nums[j]});
while(i<j && nums[j]==nums[j-1]) j--;
while(i<j && nums[i]==nums[i+1]) i++;
j--;i++;
}else if(nums[i]+nums[j]<target) i++;
else j--;
}
}
return ret;
}
};
參考:
http://www.cnblogs.com/grandyang/p/4481576.html