leetcode_rust/problems/p000_0xx/
p000_016.rs

1//! # Description
2//!
3//! Given an integer array nums of length `n` and an integer `target`,
4//! find three integers in nums such that the sum is closest to `target`.
5//!
6//! Return the _sum of the three integers_.
7//!
8//! You may assume that each input would have exactly one solution.
9//!
10//! Example 1:
11//!
12//! ```plain
13//! Input: nums = [-1,2,1,-4], target = 1
14//! Output: 2
15//! Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
16//! ```
17//!
18//! Example 2:
19//!
20//! ```plain
21//! Input: nums = [0,0,0], target = 1
22//! Output: 0
23//! Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
24//! ```
25//!
26//! Constraints:
27//!
28//! - `3 $\leqslant$ nums.length $\leqslant$ 500`
29//! - `-1000 $\leqslant$ nums[i] $\leqslant$ 1000`
30//! - `$-10^4$ $\leqslant$ target $\leqslant$ $10^4$`
31//!
32//! Sources: <https://leetcode.com/problems/3sum-closest/>
33
34////////////////////////////////////////////////////////////////////////////////
35
36/// 3Sum Closest
37///
38/// # Arguments
39/// * `nums` - input number pairs
40/// * `target` - the expected target number
41pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
42    algorithm(nums, target)
43}
44
45#[allow(unused_assignments)]
46fn algorithm(nums: Vec<i32>, target: i32) -> i32 {
47    let mut sorted_nums = nums;
48    sorted_nums.sort();
49
50    let mut res = sorted_nums.iter().take(3).sum();
51    if res >= target {
52        return res;
53    }
54
55    let mut i = 0;
56    let mut last_diff = ((target - res) as i32).abs();
57    let mut this_diff = 0;
58    while i <= sorted_nums.len() - 3 {
59        let mut j = i + 1;
60
61        let mut k = sorted_nums.len() - 1;
62
63        while j < k {
64            let temp = sorted_nums[i] + sorted_nums[j] + sorted_nums[k];
65            if temp == target {
66                return temp;
67            }
68
69            if temp <= target {
70                j += 1;
71                this_diff = target - temp;
72            } else {
73                k -= 1;
74                this_diff = temp - target;
75            }
76            // Should not be possible to overflow.
77            if this_diff <= last_diff {
78                res = temp;
79                last_diff = this_diff;
80            }
81        }
82
83        i += 1;
84    }
85
86    res
87}
88
89#[cfg(test)]
90mod tests {
91    use super::three_sum_closest;
92
93    #[test]
94    fn test_three_sum_closest() {
95        assert_eq!(three_sum_closest(vec![-1, 2, 1, -4], 1), 2);
96        assert_eq!(three_sum_closest(vec![0, 0, 0], 1), 0);
97        assert_eq!(three_sum_closest(vec![0, 1, 2], 0), 3);
98    }
99}
leetcode_rust/problems/p000_0xx/p000_016.rs

leetcode_rust/problems/p000_0xx/
p000_016.rs
