題目
給出一個有n個整數(shù)的數(shù)組S，在S中找到三個整數(shù)a, b, c酪耳，找到所有使得a + b + c = 0的三元組铡恕。
注意事項(xiàng)
在三元組(a, b, c)，要求a <= b <= c脏答。
結(jié)果不能包含重復(fù)的三元組糕殉。
樣例
如S = {-1 0 1 2 -1 -4}, 你需要返回的三元組集合的是：
(-1, 0, 1)
(-1, -1, 2)
分析
從第一個元素開始，找剩下兩個元素殖告，分別用兩根指針一頭一尾阿蝶，慢慢靠近。
具體看代碼里的注釋
代碼
public class Solution {
/**
* @param numbers : Give an array numbers of n integer
* @return : Find all unique triplets in the array which gives the sum of zero.
*/
public ArrayList<ArrayList<Integer>> threeSum(int[] nums) {
//先將數(shù)組排序黄绩，由小到大羡洁，然后依次從第一個元素開始，兩根指針爽丹，一頭一尾遍歷筑煮，如果找到等于target也就是0的就add進(jìn)結(jié)果。
//判斷邊界情況粤蝎，當(dāng)nums為空或者null的時(shí)候
if(nums == null || nums.length == 0) {
return null;
}
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
//首先對數(shù)組進(jìn)行排序
Arrays.sort(nums);
//從第一個元素開始循環(huán)
for(int i=0;i<nums.length-2;i++) {
//優(yōu)化情況真仲，如果兩個或多個元素相等判斷一次就行了，相等的元素可以直接跳過
if(i != 0 && nums[i] == nums[i-1])
continue;
//設(shè)置兩個指針一頭一尾開始找
int left = i+1;
int right = nums.length-1;
//兩根指針沒相遇時(shí)尋找
while(left < right) {
int sum = nums[i] + nums[left] + nums[right];
if(sum > 0)
right--;
else if(sum < 0)
left++;
else{
ArrayList<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(nums[left]);
temp.add(nums[right]);
res.add(temp);
left++;
right--;
//同樣可以優(yōu)化初澎，如果有相等的元素判斷一次就可以
while(left<right && nums[left] == nums[left-1])
left++;
while(left<right && nums[right] == nums[right+1])
right--;
}
}
}
return res;
}
}
