剑指offer 7 数组中和为0的三个数

此问题属于nsum问题，题目链接：力扣

要求在数组中找到不重复的三元组，三个数加起来为0，且每个下标只能用一次。而且需要返回所有这样的不重复数组。

1. 排序 + 双指针

1. 「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：

• 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
• 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说，我们枚举的三元组 (a, b, c) 满足 a ≤ b ≤ c，保证了只有 (a, b, c) 这个顺序会被枚举到，而(b, a, c)、(c, b, a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。

2. 对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复，（但是对于初学者来讲，为了简化题目，可以先不考虑重复结果的处理）

2. 不考虑重复

我们可以先考虑不处理重复结果的情况，代码如下：（注释全整版）：

    public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums); // 排序是前提List<List<Integer>> ans = new ArrayList<>();// 枚举 afor (int a = 0; a < n; a++) {int c = n - 1; // 将c初始指向数组最后一位int target = -nums[a]; // 这是b和c的目标和for (int b = a + 1; b < n; b++) { // b 暂时固定（按部就班的递增）while (b < c && nums[b] + nums[c] > target){c--;}// 如果b和c的和太大，c就左移if (c == b) break; // a b 确定下，c已经退无可退了，所以break// 后续就算是b再递增，这个总和也是太大，没有合适的c了if (nums[b] + nums[c] == target){List<Integer> list = new ArrayList<>();list.add(nums[a]);list.add(nums[b]);list.add(nums[c]);ans.add(list);}}}return ans;}

其实不加处理重复的话，代码很简单哈哈！！！

3.加上对重复的判定

后续对于重复答案的处理，就是要求a不重复，b不重复，在代码中分别加上这两段验证即可：

1. 对于a： 

if (a > 0 && nums[a] == nums[a - 1]) continue;

2. 对于b

if (b > a + 1 &&  nums[b] == nums[b - 1]) continue;

由以上思路得出的本题目的完整版代码如下：（注释完整版）

class Solution {public List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> res = new ArrayList<>();for (int a = 0; a < n; a++) {if (a > 0 && nums[a] == nums[a - 1]) continue; // 每个数只能当一次aint c = n - 1;int target = -nums[a];// 枚举bfor (int b = a + 1; b < n; b++) { // b从a后一个开始if (b > a + 1 && nums[b] == nums[b - 1]) continue; // b > a+1代表// 比如说 0 1 1这个数组，如果a指向0，b指向第二个1，那就没必要了// 因为每个数字只能当一次bwhile (b < c && nums[b] + nums[c] > target) {--c;}// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if (b == c) {break;}if (nums[b] + nums[c] == target) {List<Integer> list = new ArrayList<Integer>();list.add(nums[a]);list.add(nums[b]);list.add(nums[c]);res.add(list);}}}return res;}
}

时间复杂度，在n <= 3000的数据范围内可以满足要求