双指针：三数之和

题目描述：求一个整形数组中，构成三数之和为0的所有互不相同的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

解释：虽然-1有两个，即[-1,0,1]的三元组有两个，但只返回一个。

求解思路1：使用哈希方法求解两数之和的思路，细节是处理重复值，直接使用set存结果集。

class Solution {public List<List<Integer>> threeSum(int[] nums) {// 求两数之和时，用的hash表HashSet<Integer> hash = new HashSet<>();// 存放最终的结果集Set<List<Integer>> record = new HashSet<>();// 第一层循环，确定第一个数for (int i = 0; i < nums.length; i++) {int twoSum = -nums[i];// 求两数之和的过程for (int j = i + 1; j < nums.length; j++) {int oneSum = twoSum - nums[j];// 判断差的数是否存在// 我的思想误区，解释下：因为是先判断找的差值，再存当前的数，不存在[3],6=target=3+3这种情况if (hash.contains(oneSum)) { List<Integer> arr = new ArrayList<>();arr.add(nums[i]);arr.add(nums[j]);arr.add(oneSum);Collections.sort(arr);record.add(arr);}// 把当前的数放进去hash.add(nums[j]);}hash.clear();}return new ArrayList<>(record);}
}

巩固一下：可以使用Set构造List，最终得到的是唯一的值的List。转换方法：

使用new ArrayList<>(HashSet)或new LinkedList<>(HashSet)即可将HashSet转换为List。例如：

HashSet<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");
List<String> list = new ArrayList<>(hashSet);

求解思路2：排序(为了二分查找)+两数之和+双指针

class Solution {public List<List<Integer>> threeSum(int[] nums) {int len = nums.length;Set<List<Integer>> record = new HashSet<>();Arrays.sort(nums);for (int i = 0; i < len; i++) {int twoSum = -nums[i];int left = i + 1;int right = len - 1;while (left < right) {if (twoSum == nums[left] + nums[right]) {List<Integer> arr = new ArrayList<>();arr.add(nums[left]);arr.add(nums[right]);arr.add(nums[i]);Collections.sort(arr);record.add(arr);// 固定left或者right，寻找到的都是重复的，所以双指针同时走left++;right--;} else if (twoSum > nums[left] + nums[right]) {left++;} else if (twoSum < nums[left] + nums[right]) {right--;}}}return new ArrayList<>(record);}
}

练习地址：15. 三数之和 - 力扣（LeetCode）