文章目录
16. 定制开发最接近的三数之和：
定制开发给你一个长度为 n 定制开发的整数数组 nums 和 定制开发一个目标值 target。请你从 nums 定制开发中选出三个整数，定制开发使它们的和与 target 最接近。
定制开发返回这三个数的和。
假定每组输入只存在恰好一个解。
样例 1：
输入： nums = [-1,2,1,-4], target = 1 输出： 2 解释： 与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
样例 2：
输入： nums = [0,0,0], target = 1 输出： 0- 1
- 2
- 3
- 4
- 5
提示：
- 3 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- -104 <= target <= 104
原题传送门：
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 这道题和【15. 三数之和】很像，但是不再是找一个值，而是要把可能的值都找一遍，最后确定最接近的值，所以不再是直接跳过大于目标，或者小于目标的值。
- 由于有三个变量，直观的做法还是暴力三层循环，但还是传说会超时。
- 同样我们先排个序，可以外层循环遍历作为第一个数。
- 这里用到双指针的思想，如果是找最接近的两数之和，我们可以将两个指针先定位在有序数组的两端，去判断两数之和是否和目标相等，如果相等就是想要的结果；如果大于目标，我们向左移动右面的指针；如果小于目标，我们就向右移动左边的指针。（如果右面的指针一直向左移动就会让两数之和最小，反之如果让左面的指针一直向右移动就会使两数之和最大，这样两个指针的移动方向虽然固定了，但是却不会漏掉某种组合）
- 扩展到三数之和，由于外层循环已经确定了第一个数的值，内层其实就是最接近的两数之和。
题解
rust
impl Solution { pub fn three_sum_closest(mut nums: Vec<i32>, target: i32) -> i32 { let n = nums.len(); nums.sort(); let mut ans = 23001; for f in 0..n { if f == 0 || nums[f] != nums[f - 1] { let mut s = f + 1; let mut t = n - 1; while s < t { let sum = nums[f] + nums[s] + nums[t]; if sum == target { return target; } if (sum - target).abs() < (ans - target).abs() { ans = sum; } if sum > target { let mut t0 = t - 1; while s < t0 && nums[t0] == nums[t] { t0 -= 1; } t = t0; } else { let mut s0 = s + 1; while s0 < t && nums[s0] == nums[s] { s0 += 1; } s = s0; } } } } return ans; }}- 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
go
func threeSumClosest(nums []int, target int) int { n := len(nums) sort.Ints(nums) ans := 23001 abs := func(num int) int { if num < 0 { return -num } return num } for f := 0; f < n; f++ { if f > 0 && nums[f] == nums[f-1] { continue } s, t := f+1, n-1 for s < t { sum := nums[f] + nums[s] + nums[t] if sum == target { return target } if abs(sum-target) < abs(ans-target) { ans = sum } if sum > target { t0 := t - 1 for s < t0 && nums[t0] == nums[t] { t0 -= 1 } t = t0 } else { s0 := s + 1 for s0 < t && nums[s0] == nums[s] { s0 += 1 } s = s0 } } } return ans}- 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
- 39
- 40
- 41
- 42
- 43
c++
class Solution {public: int threeSumClosest(vector<int>& nums, int target) { int n = nums.size(); sort(nums.begin(), nums.end()); int ans = 23001; for (int f = 0; f < n; ++f) { if (f > 0 && nums[f] == nums[f - 1]) { continue; } int s = f + 1; int t = n - 1; while (s < t) { int sum = nums[f] + nums[s] + nums[t]; if (sum == target) { return target; } if (abs(sum - target) < abs(ans - target)) { ans = sum; } if (sum > target) { int t0 = t - 1; while (s < t0 && nums[t0] == nums[t]) { t0 -= 1; } t = t0; } else { int s0 = s + 1; while (s0 < t && nums[s0] == nums[s]) { s0 += 1; } s = s0; } } } return ans; }};- 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
java
class Solution { public int threeSumClosest(int[] nums, int target) { int n = nums.length; Arrays.sort(nums); int ans = 23001; for (int f = 0; f < n; ++f) { if (f > 0 && nums[f] == nums[f - 1]) { continue; } int s = f + 1; int t = n - 1; while (s < t) { int sum = nums[f] + nums[s] + nums[t]; if (sum == target) { return target; } if (Math.abs(sum - target) < Math.abs(ans - target)) { ans = sum; } if (sum > target) { int t0 = t - 1; while (s < t0 && nums[t0] == nums[t]) { t0 -= 1; } t = t0; } else { int s0 = s + 1; while (s0 < t && nums[s0] == nums[s]) { s0 += 1; } s = s0; } } } return ans; }}- 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
typescript
function threeSumClosest(nums: number[], target: number): number { const n = nums.length; nums.sort((a, b) => a - b); let ans = 23001; for (let f = 0; f < nums.length; ++f) { if (f > 0 && nums[f] === nums[f - 1]) { continue; } let s = f + 1; let t = n - 1; while (s < t) { const sum = nums[f] + nums[s] + nums[t]; if (sum === target) { return target; } if (Math.abs(sum - target) < Math.abs(ans - target)) { ans = sum; } if (sum > target) { let t0 = t - 1; while (s < t0 && nums[t0] === nums[t]) { t0 -= 1; } t = t0; } else { let s0 = s + 1; while (s0 < t && nums[s0] === nums[s]) { s0 += 1; } s = s0; } } } return ans;};- 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
python
class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: n = len(nums) nums.sort() ans = 23001 for f in range(n): if f > 0 and nums[f] == nums[f - 1]: continue s = f + 1 t = n - 1 while s < t: sum = nums[f] + nums[s] + nums[t] if sum == target: return target if abs(sum - target) < abs(ans - target): ans = sum if sum > target: t0 = t - 1 while s < t0 and nums[t0] == nums[t]: t0 -= 1 t = t0 else: s0 = s + 1 while s0 < t and nums[s0] == nums[s]: s0 += 1 s = s0 return ans- 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
非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 博客原创~