16. 3Sum Closest Medium

1/**
2 * [16] 3Sum Closest
3 *
4 * Given an array nums of n integers and an integer target, find three
5 * integers in nums such that the sum is closest to target. Return the
6 * sum of the three integers. You may assume that each input would
7 * have exactly one solution.
8 *  
9 * Example 1:
10 *
11 * Input: nums = [-1,2,1,-4], target = 1
12 * Output: 2
13 * Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
14 *
15 *  
16 * Constraints:
17 *
18 * 3 <= nums.length <= 10^3
19 * -10^3 <= nums[i] <= 10^3
20 * -10^4 <= target <= 10^4
21 *
22 */
23pub struct Solution {}
24
25// problem: https://leetcode.com/problems/3sum-closest/
26// discuss: https://leetcode.com/problems/3sum-closest/discuss/?currentPage=1&orderBy=most_votes&query=
27
28// submission codes start here
29
30impl Solution {
31    pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
32        let mut min_diff = i32::MAX;
33        let mut result = 0;
34        let mut data = nums.clone();
35        data.sort();
36
37        for i in 0..data.len() - 2 {
38            if i != 0 && data[i] == data[i - 1] {
39                continue;
40            }
41
42            let mut s = i + 1;
43            let mut e = data.len() - 1;
44            while s < e {
45                while s != i + 1 && data[s - 1] == data[s] && s + 1 < e {
46                    s += 1
47                }
48                while e != data.len() - 1 && data[e + 1] == data[e] && e - 1 > s {
49                    e -= 1
50                }
51
52                let new_sum = data[s] + data[e] + data[i];
53                let diff = (new_sum - target).abs();
54                if diff < min_diff {
55                    min_diff = diff;
56                    result = new_sum;
57                }
58
59                if new_sum < target {
60                    s += 1;
61                } else if new_sum == target {
62                    return target;
63                } else {
64                    e -= 1;
65                }
66            }
67        }
68
69        result
70    }
71}
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_16() {
81        assert_eq!(Solution::three_sum_closest(vec![-1, 2, 1, -4], 1), 2);
82        assert_eq!(Solution::three_sum_closest(vec![0, 2, 1, -3], 1), 0);
83        assert_eq!(Solution::three_sum_closest(vec![1, 1, -1, -1, 3], -1), -1);
84        assert_eq!(Solution::three_sum_closest(vec![-1, 0, 1, 1, 55], 3), 2);
85        assert_eq!(Solution::three_sum_closest(vec![3, 4, 5, 5, 7], 13), 13);
86    }
87}
88