排序 + 双指针

思路： 先将数组排序，再从数组中取出一个元素。使用两个指针从该元素之后取出一小一大两个元素，如果当前三个元素相加不为0，那么调整两个指针的位置继续求和。如果为0则将三个元素加入结果中。

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); int n = nums.length; if (n < 3) { return res; } Arrays.sort(nums); for (int i = 0; i < n - 2; i++) { int left = i + 1, right = n - 1; int target = -nums[i]; if (nums[i] > 0) break; if (i > 0 && nums[i] == nums[i - 1]) // 与上一轮得值相等可以直接跳过 continue; while (left < right) { if (nums[left] + nums[right] > target) { right--; } else if (nums[left] + nums[right] < target) { left++; } else { List<Integer> one = new ArrayList<>(); one.add(nums[i]); one.add(nums[left]); one.add(nums[right]); res.add(one); while (left < right && nums[left] == nums[left + 1]) { left++; } while (left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } } } return res; } }