力扣15三数之和（排序 + 双指针）

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;

// 先把数组升序排序，是双指针的前提，方便去重和移动指针
Arrays.sort(nums);

List<List<Integer>> ans = new ArrayList<List<Integer>>();

//枚举第一个数
for (int first = 0; first < n; ++first) {
// a去重：如果当前a和上一轮a相同，直接跳过，避免产出一样的三元组
if (first > 0 && nums[first] == nums[first – 1]) {
continue;
}

int third = n – 1;

// 目标：b + c = -a，也就是 a+b+c=0
int target = -nums[first];

// 枚举第二个数
for (int second = first + 1; second < n; ++second) {
// b去重
if (second > first + 1 && nums[second] == nums[second – 1]) {
continue;
}

// 核心双指针：b+c > target，说明c太大了，c左移变小
// 条件 second < third：必须保证b在c左边，不能重合
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;
}
}