https://leetcode-cn.com/problems/3sum/
排序 + 双指针
- 拆解成两数之和的问题
- 遍历，第一个数固定，剩下的就是两数之和问题了
```java
public List> threeSum(int[] nums) {
Arrays.sort(nums);
List> ans = new ArrayList<>();
// 第一个数选了i位置的数
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || nums[i] != nums[i - 1]) { List<List<Integer>> nexts = twoSum(nums, i + 1, -nums[i]); for (List<Integer> cur : nexts) { cur.add(0, nums[i]); // 这里针对arraylist每次都插头代价略高，可以想想怎么优化 --> 从右到左搞呗 ans.add(cur); } }
}
return ans;
}
// nums已经有序了
// nums[begin……]范围上，找到累加和为target的所有二元组
public List> twoSum(int[] nums, int begin, int target) {
int L = begin;
int R = nums.length - 1;
List> ans = new ArrayList<>();
while (L < R) {
if (nums[L] + nums[R] > target) {
R—;
} else if (nums[L] + nums[R] < target) {
L++;
} else {
if (L == begin || nums[L - 1] != nums[L]) {
List cur = new ArrayList<>();
cur.add(nums[L]);
cur.add(nums[R]);
ans.add(cur);
}
L++;
}
}
return ans;
}
```
