15. 三数之和 | LeetCode

思路

首先对 nums 进行排序，然后设置三个指针：left、mid、right：

• left 从最左边开始，依次向后遍历
• 每次固定住 left 后，就化为一个 2sum 问题：
  • mid = left + 1，right = nums.length - 1，计算 sum
  • 如果 sum 大于 0，则 right 向后走；如果 sum 小于 0，则 mid 向前走；等于 0 则加入结果集并让 right 和 mid 均走一步

注意点：

• ⚠️ left、mid、right 在向前或者向后走一步时，都要直接跳过重复值，防止产生重复解
• 在 nums[left] 的值大于 0 的情况下，三数之和不可能再为 0，所以可以提前结束

参考思路：

• 一个函数秒杀 2Sum 3Sum 4Sum 问题 | labuladong
• 三数之和（排序+双指针，易懂图解）| LeetCode

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int left = 0, right = nums.length - 1, mid = 0;List<List<Integer>> results = new ArrayList<>();while (true) {// special caseif (left > nums.length - 2) {return results;}if (left != 0 && nums[left] == nums[left - 1]) {left++;continue;}if (nums[left] > 0) {  // left 的值大于 0，表示 3sum 不可能再是 0return results;}// 固定住 left，化为解 2sum 问题mid = left + 1;right = nums.length - 1;while (mid < right) {int sum = nums[left] + nums[mid] + nums[right];if (sum > 0) {right--;while (right > mid && nums[right] == nums[right + 1]) {  // 跳过重复值right--;}} else if (sum < 0) {mid++;while (mid < right && nums[mid] == nums[mid - 1]) {  // 跳过重复值mid++;}} else {results.add(List.of(nums[left], nums[mid], nums[right]));right--;while (right > mid && nums[right] == nums[right + 1]) {  // 跳过重复值right--;}mid++;while (mid < right && nums[mid] == nums[mid - 1]) {  // 跳过重复值mid++;}}}left++;}}
}