三数之和

1、参考资料

https://leetcode-cn.com/problems/3sum/

https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/

2、题目要求

题目要求：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0，请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

3、代码思路

之前尝试过的方法

暴力匹配可以，三层 for 循环带给我们的是 O(n³) 的复杂度，我们还需要将三个数按照从小到大的顺序排列，并使用 HashMap 进行去重操作，得到不包含重复三元组的最终答案因为 (a, b, c)、(b, a, c)、(b, c, a) 属于重复的三元组，匹配之后我们需要进行排序、去重操作

---

排序 + 双指针

我们首先要理解不重复的本质是什么？我们先将数组排序，然后在数组中找出三个数 a、b、c，满足其和：a + b + c = 0，其中 a <= b <= c，这样保证了只有 (a, b, c) 这样的顺序，不会出现 (b, a, c) 或者 (b, c, a) 这样的顺序，这样我们就不用对三元组进行去重操作但是这样做我们始终没有跳出三层 for 循环的思想，实际上第二重 + 第三重循环我们可以使用一层 while 循环 + 双指针来替代left = i + 1 为左指针(i 最外层 for 循环的计数器)，right = nums.length - 1 为右指针。当 left 增加，right 不变时，三数之和增大；当 right 减小，left 不变时，三数之和减小；我们利用这个特点，可以将原来两层 for 循环变为一层 while 循环，即我们可以通过双指针的方式将内层循环的复杂度从 O(n²) 降为 O(n)为了保证得到的三元组为不重复的三元组，对于数 a，我们每次在 for 循环中都判断数 a 是否与上次的值相同，如果相同，则跳过本次循环，对于 left 和 right，我们每次在外层 for 开始时，将 left 重置为 i + 1，将 right 重置为 nums.length - 1，在匹配到三数之和等于 0 时，将 left 右移至与上次元素值不同的位置，将 right 左移至与上次元素值不同的位置(保证三元组不重复)

4、代码实现

代码

/** * @ClassName ThreeSumDemo * @Description TODO * @Author Heygo * @Date 2020/9/2 17:11 * @Version 1.0 */ public class ThreeSumDemo { public static void main(String[] args) { List<List<Integer>> res = threeSum(new int[]{-1, 0, 1, 2, -1, -4}); System.out.println(res); } public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); // Guard Safe if (nums == null || nums.length <= 2) { return result; } // 先对数组进行排序，后面才能方便地进行判断是否重复 Arrays.sort(nums); // 遍历数组，当 i = nums.length - 3时，left = nums.length - 2，right = nums.length - 1，为临界条件 for (int i = 0; i < nums.length - 2; i++) { // 如果当前元素大于 0，证明已经将数组中三数之和等于 3 的元素都找出来了，直接跳出循环 if (nums[i] > 0) { break; } // 上一次的元素和当前相同，跳过此次循环 if (i > 0 && nums[i] == nums[i - 1]) { continue; } int target = -nums[i]; // 目标值 int left = i + 1; // left 指针 int right = nums.length - 1; // right 指针 // 当 left < right 时，证明还有元素待验证 while (left < right) { if (nums[left] + nums[right] == target) { // 如果三数之和等于 0，则将这三个数加入集合中 result.add(Arrays.asList(nums[i], nums[left], nums[right])); left++; // 左指针右移 right--; // 右指针左移 // 左指针需要移动至下一个与上次元素值不相同的位置 while (left < right && nums[left] == nums[left - 1]) { left++; } // 右指针需要移动至下一个与上次元素值不相同的位置 while (left < right && nums[right] == nums[right + 1]) { right--; } } else if (nums[left] + nums[right] < target) { // 否则三数之和小于目标值，则 left++，尝试增大三数之和 left++; } else { // 否则三数之和大于目标值，则 right--，尝试减小三数之和 right--; } } } return result; } }