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}