双指针简化数组遍历
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
思路:
遍历方式跟上一道题雷同。先快速排序,再一层遍历+一层双指针。修改一下更新最佳值的条件即可,要求target和当前三数和的差值的绝对值尽可能小。
偷懒的话,可以不进行最后的指针优化(跳过重复元素),复杂度还是一样的。
时间复杂度:O(n²)
空间复杂度:O(1)
实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length; int closestSum = nums[0] + nums[1] + nums[2]; for (int i = 0; i < n; i++) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1, k = n - 1; j < k;) { int curSum = nums[i] + nums[j] + nums[k]; if (curSum == target) { return target; } if (Math.abs(curSum - target) < Math.abs(closestSum - target)) { closestSum = curSum; } if (curSum > target) { int k0 = k - 1; while (j < k0 && nums[k0] == nums[k]) { --k0; } k = k0; } else { int j0 = j + 1; while (j0 < k && nums[j0] == nums[j]) { ++j0; } j = j0; } } } return closestSum; } }
|