15. 3Sum
題目大意
給定一個(gè)數(shù)組憋他，要求找出所有和為0的三個(gè)數(shù)的集合，不能重復(fù)髓削。
雙指針?lè)?br>
空間:O(n) 時(shí)間:O(n^2)
Youtube 講解
閉著眼睛也要記得的解法
// [nums[i], low, high] = 0
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); //一定要sort
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i< nums.length -2; i++){
if(i> 0 && nums[i-1] == nums[i]) continue; //去重nums[i]
int low = i+1;
int high = nums.length-1;
int sum = 0 - nums[i];//即 從這里開(kāi)始是low和high的two sum
while(low < high){
if(nums[low] + nums[high] == sum){ //找到了
res.add(Arrays.asList(nums[i],nums[low],nums[high])); //記住 Array.aslist()這種方法Ｖ竦病！
while(low < high && nums[low+1] == nums[low] ) low++;//去重nums[low]
while(low < high && nums[high -1] == nums[high]) high--;//去重nums[high]
low ++;
high--;
}else if(nums[low] + nums[high] < sum){
low++;
}else high --;
}
}
return res;
}
}
