leetcode_rust/problems_cn/p000_0xx/
p000_016.rs

1//! # 问题描述
2//!
3//! 给你一个长度为 `n` 的整数数组 `nums` 和 一个目标值 `target`。请你从 `nums` 中选出三个
4//! 整数，使它们的和与 `target` 最接近。
5//!
6//! 返回这三个数的和。
7//!
8//! 假定每组输入只存在恰好一个解。
9//!
10//! 示例 1：
11//!
12//! ```plain
13//! 输入：nums = [-1,2,1,-4], target = 1
14//! 输出：2
15//! 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
16//! ```
17//!
18//! 示例 2：
19//!
20//! ```plain
21//! 输入：nums = [0,0,0], target = 1
22//! 输出：0
23//! ```
24//!
25//! 提示：
26//!
27//! - `3 $\leqslant$ nums.length $\leqslant$ 1000`
28//! - `-1000 $\leqslant$ nums[i] $\leqslant$ 1000`
29//! - `$-10^4$ $\leqslant$ target $\leqslant$ $10^4$`
30//!
31//! 来源：<https://leetcode.cn/problems/3sum-closest/>
32
33////////////////////////////////////////////////////////////////////////////////
34
35/// 最接近的三数之和
36///
37/// # 参数
38/// * `nums` - 传入数字序列
39/// * `target` - 期望靠近的目标值
40pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
41    algorithm(nums, target)
42}
43
44#[allow(unused_assignments)]
45fn algorithm(nums: Vec<i32>, target: i32) -> i32 {
46    let mut sorted_nums = nums;
47    sorted_nums.sort();
48
49    let mut res = sorted_nums.iter().take(3).sum();
50    if res >= target {
51        return res;
52    }
53
54    let mut i = 0;
55    let mut last_diff = ((target - res) as i32).abs();
56    let mut this_diff = 0;
57    while i <= sorted_nums.len() - 3 {
58        let mut j = i + 1;
59
60        let mut k = sorted_nums.len() - 1;
61
62        while j < k {
63            let temp = sorted_nums[i] + sorted_nums[j] + sorted_nums[k];
64            if temp == target {
65                return temp;
66            }
67
68            if temp <= target {
69                j += 1;
70                this_diff = target - temp;
71            } else {
72                k -= 1;
73                this_diff = temp - target;
74            }
75            // 由于改用提前计算差值的办法，所以不会溢出。
76            if this_diff <= last_diff {
77                res = temp;
78                last_diff = this_diff;
79            }
80        }
81
82        i += 1;
83    }
84
85    res
86}
87
88#[cfg(test)]
89mod tests {
90    use super::three_sum_closest;
91
92    #[test]
93    fn test_three_sum_closest() {
94        assert_eq!(three_sum_closest(vec![-1, 2, 1, -4], 1), 2);
95        assert_eq!(three_sum_closest(vec![0, 0, 0], 1), 0);
96        assert_eq!(three_sum_closest(vec![0, 1, 2], 0), 3);
97    }
98}
leetcode_rust/problems_cn/p000_0xx/p000_016.rs

leetcode_rust/problems_cn/p000_0xx/
p000_016.rs
