力扣15.三数之和

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<>();int n = nums.length;for (int i = 0; i < n-2; i++) {int x = nums[i];if (i > 0 && x == nums[i-1]) continue;if (x + nums[i+1] + nums[i+2] > 0) break;if (x + nums[n-1] + nums[n-2] < 0) continue;int j = i + 1;int k = n - 1;while (j < k) {int s = x + nums[j] + nums[k];if (s > 0) {k--;} else if (s < 0) {j++;} else {ans.add(List.of(x, nums[j], nums[k]));j++;k--;while (j < k && nums[j] == nums[j-1]) {j++;}while (k > j && nums[k] == nums[k+1]) {k--;}}} }return ans;}
}

• 有两层循环，第一层枚举第一个数，第二层双指针向内进行查找
• 解决重复问题：先进行排序，对于外层nums[i]和nums[i-1]进行比较，如果相同直接continue跳过，内层的nums[i]和nums[j]也是如此比较跳过重复部分
• 两个优化，如果if (x + nums[i+1] + nums[i+2] > 0) break;如果紧邻的两个数相加都>0说明后面更大的数肯定更大，就没必要再比较了；if (x + nums[n-1] + nums[n-2] < 0) continue;如果这个最外层的nums[i]和最大的两个数都还<0，说明最外层的这个数字需要变得更大，直接continue进行下一个计算