三数之和
给你一个包含 n 个整数的数组 nums，target，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = target？请你找出所有和为 target且不重复的三元组。
示例 ：
输入：nums = [5,12,6,3,9,2,1,7] target= 13 输出：[[5,6,2],[5,1,7],[3,9,1]]
思路1
有了前文两数之和题目的铺垫，首先想到了固定某一个值，然后求两数之和为剩余值
比如固定住第一个数字5，然后在其他数字中求两数之和为13-5=8的两个数字
public static List<List<Integer>> threeSum(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { int need = target - nums[i]; //两数之和过程 Map<Integer, Integer> data = new HashMap<>(); for (int j = i + 1; j < nums.length; j++) { int d2 = need - nums[j]; if (data.containsKey(d2)) { result.add(Arrays.asList(nums[i], nums[j], d2)); } data.put(nums[j], j); } } return result; }
这种方式是可以完成此题，但是算法复杂度是O(n²)，空间复杂度是O(n)(用于多次构建两数之和map)
同时有点硬靠两数之和解法的嫌疑
缺点是空间复杂度偏大，想办法把空间复杂度降低到O(1)
思路2
其实三数之和已经失去了用hash快速定位的优势，如果硬板前面解法反而浪费了空间，需要多次构建hash表
此时不必拘泥于前面的解法
采用排序+双指针解法
public static List<List<Integer>> threeSum2(int[] nums, int target) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { int need = target - nums[i]; //查找剩余两数之和为need的数字 //由于是已经排序的数组，可以使用头尾两个指针来控制，之和的大小 for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) { //如果两数之和大于need，所以右指针左移，也就是向着变小的方向移动k--才有可能找到答案 //如果两数之和小于need，所以左指针右移，也就是向着变大的方向以移动j++ while (j < k && nums[j] + nums[k] > need) { k--; } //遍历结束 if (j == k) { break; } //发现满足条件的答案 if (nums[j] + nums[k] == need) { result.add(Arrays.asList(nums[i], nums[j], nums[k])); } } } return result; }
- 貌似是三层循环，但每一轮指针j和k的移动次数加起来最多n-1次，因此该解法的整体时间复杂度是O（n²）。
- 最关键的是，该解法并没有使用额外的集合（排序是直接在输入数组上进行的），所以空间复杂度只有O（1）
另一种三数之和
给你一个包含 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] 输出：[]
思路
这道题完全可以看成，第一道题目三数之和的特殊版本，也就是target=0的版本
换成while循环重写一遍，其实是一样的思路
public static List<List<Integer>> threeSum2(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { int need = -nums[i]; //查找剩余两数之和为need的数字 //由于是已经排序的数组，可以使用头尾两个指针来控制，之和的大小 int j = i + 1, k = nums.length - 1; while (j < k) { //如果两数之和大于need，所以右指针左移，也就是向着变小的方向移动k--才有可能找到答案 //如果两数之和小于need，所以左指针右移，也就是向着变大的方向以移动j++ while (j < k && nums[j] + nums[k] > need) { k--; } //遍历结束 if (j == k) { break; } //发现满足条件的答案 if (nums[j] + nums[k] == need) { result.add(Arrays.asList(nums[i], nums[j], nums[k])); } j++; } } return result; }
最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
思路
做了三数之和题目后看到此题目想到的还是用排序+双指针方式，试着把这个思路实现
用了差不多十分钟写的并没有通过，感觉思路还是不顺
public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int result = nums[0] + nums[1] + nums[2]; for (int i = 0; i < nums.length; i++) { for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) { int nextSum = nums[i] + nums[j] + nums[k]; while (j < k) { if (Math.abs((target - nextSum)) < Math.abs(target - result)) { result = nextSum; } if (target - nextSum > 0) { k--; } } } } return result; }
查看下大鹏的题解，真是太漂亮了，思路清晰、逻辑缜密，环环相扣
public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); //初始和 int ans = nums[0] + nums[1] + nums[2]; for(int i=0;i<nums.length;i++) { //双指针 int start = i+1, end = nums.length - 1; while(start < end) { int sum = nums[start] + nums[end] + nums[i]; if(Math.abs(target - sum) < Math.abs(target - ans)) ans = sum; if(sum > target) end--; else if(sum < target) start++; else return ans; } } return ans; }
小结
双指针算法题目还是很多的，第一次看到时感觉太巧妙了，现在看来也是能解决很多问题，接下来会尝试做一些相同题型的题目。
