三数之和
题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]
提示：
0 <= nums.length <= 3000 -105 <= nums[i] <= 105
题目分析
1. 暴力解题
时间复杂度：O(N * N *N)
空间复杂度：O(1)
直接通过三重循环来计算。
2. 优化思路
时间复杂度：O(N * N *N)
空间复杂度：O(logN)
解题关键：排序 + 双指针。
题目中要求是不能重复的， 我们可以将输入的整个数组先排序来防止重复。
选择双指针的思路是，我们三个数的和其实可以先取出一个数，然后就看作两个数的和来处理，这样就可以灵活的运用双指针的思路了。
双指针过程中的指针移动。a , b, c 下标的移动过程中。
- a 下标需要遍历数组，得到 b + c 的和等于 -1 * a，需要通过前一个来判断是否是重复，如果已经存在就跳过。
- b, c 双指针的移动过程，首先 b 指针初始化，为 a 下标 + 1； 并且通过前一个数来判断数据是否存在重复，如果已经存在就跳过。
- c 指针的初始指针位置为 nums.length -1 。如果 a + b > -a 那么就需要把 c 指针左移，否者右移 b 指针，因为已经排序了的。
- 如果 a + b == -a ， 表示找到真确的结果，存储到返回的结果集中。
- 如果 c 指针 == b 指针说明已经找了一圈了，就退出本次的循环，然后在回去移动 a 指针。
解题代码
public class NumThreeSumTest { public static void main(String[] args) { NumThreeSumTest numThreeSumTest = new NumThreeSumTest(); List<List<Integer>> lists = numThreeSumTest.threeSum(new int[]{-1,0,1,2,-1,-4}); System.out.println(lists); } public List<List<Integer>> threeSum(int[] nums) { // 数组长度 int len = nums.length; // 排序 Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); for (int first = 0; first < len; first++) { // 跳过相同的值 if (first > 0 && nums[first] == nums[first - 1]) { continue; } int third = len - 1; int target = -nums[first]; for (int second = first + 1; second < len; second++) { // 跳过相同的值 if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } // 保证 b 的指针在 c 的左边 while (second < third && nums[second] + nums[third] > target) { --third; } // 如果指针重合，随后 b 继续增加 // 如果没有满足 a + b + c = 0 , 并且 b < c 了, 退出循环 if (second == third) { break; } // 找到合适的解，放入结果集合 if (nums[second] + nums[third] == target) { result.add(Arrays.asList(nums[first], nums[second], nums[third])); } } } return result; } }
