算法leetcode｜16. 最接近的三数之和（rust重拳出击）

---

---

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
• -10⁴ <= target <= 10⁴

原题传送门：

https://leetcode.cn/problems/3sum-closest/

---

分析

• 面对这道算法题目，二当家的陷入了沉思。
• 这道题和【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

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---