在整数数组nums中，找3个元素(a+b+c)和为0的三元组。
方法1：暴力解法：三重循环 O（N^3） //超时
方法2：排序+双指针法
先排序避免重复答案，降低复杂度变为twoSum,利用双指针找到所有解。
这里说的双指针法：a确定时，b+c 的值就确定为-a。 也就是随着b增加，c减少。那么b，c一共移动的次数是O(N)
public List<List<Integer>> threeSum(int[] nums) { int n = nums.length; //先排序 Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<List<Integer>>(); //枚举a for (int first = 0; first < n; first++){ //跳过重复的数 if (first > 0 && nums[first] == nums[first -1] ) { continue; } //目标变成求和为-a 的twoSum问题 int target = -nums[first]; //c 在最右端 int third = n - 1; //枚举 b for (int second = first + 1; second <n; second++) { if (second > first+1 && nums[second] == nums[second-1]) { continue; } while (second<third && nums[second] + nums[third] > target) { third--; } if (second == third) { break; } if (nums[second] + nums[third] == target) { List<Integer> list = new ArrayList<Integer>(); list.add(nums[first]); list.add(nums[second]); list.add(nums[third]); ans.add(list); } } } return ans; }
