leetcode_rust/problems_cn/p000_0xx/
p000_016.rs1pub 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 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}