根据官方的解答：https://leetcode-cn.com/problems/3sum-closest/solution/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/

本题也有一些可以减少运行时间（但不会减少时间复杂度）的小优化。当我们枚举到恰好等于 target 的 a+b+c 时，可以直接返回 target 作为答案，因为不会有再比这个更接近的值了。

另一个优化与 15. 三数之和的官方题解 中提到的类似。当我们枚举 a, b, c 中任意元素并移动指针时，可以直接将其移动到下一个与这次枚举到的不相同的元素，减少枚举的次数。

我看的基础答案是 leetcode_memory_minimun 函数里面的这种。

然后觉得会有一些改进的空间，所以我在下面的 three_sum_closest 函数中对极端情况做了预先的处理：数组不够长、 target 落在数组能提供的最大和最小值之外。结果和 leetcode_memory_minimun 速度差不多。

然后在 three_sum_closest_skip中 继续优化：移动双指针时，遇到重复元素跳过，避免无意义的重复计算。性能就慢了。

leetcode_memory_minimun    ... bench:         166 ns/iter (+/- 84)
three_sum_closest                ... bench:         177 ns/iter (+/- 20)
three_sum_closest_skip        ... bench:         239 ns/iter (+/- 12)

代码如下：

/// https://leetcode-cn.com/problems/3sum-closest/
pub struct Solution;

impl Solution {
    pub fn three_sum_closest(mut nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();

        if n < 3 {
            return nums.iter().sum();
        }

        // let mut nums = nums.to_owned();
        nums.sort();

        let mut sum: i32;

        sum = nums.iter().take(3).sum();
        if sum > target {
            return sum;
        }

        sum = nums.iter().rev().take(3).sum();
        if sum < target {
            return sum;
        }

        sum = nums[0] + nums[1] + nums[n - 1];

        let mut right: usize;
        let mut left: usize;
        let mut temp: i32;

        for i in 0..n - 2 {
            left = i + 1;
            right = n - 1;
            while right > left {
                temp = nums[left] + nums[right] + nums[i];
                if temp == target {
                    return temp;
                } else if temp > target {
                    // slower if use `abs`
                    if temp - target < (sum - target).abs() {
                        sum = temp;
                    }
                    right -= 1;
                } else {
                    // slower if use `abs`
                    if target - temp < (sum - target).abs() {
                        sum = temp;
                    }
                    left += 1;
                }
            }
        }
        sum
    }

    pub fn three_sum_closest_skip(mut nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();

        if n < 3 {
            return nums.iter().sum();
        }

        // let mut nums = nums.to_owned();
        nums.sort();

        let mut sum: i32 = nums.iter().take(3).sum();
        if sum > target {
            return sum;
        }

        sum = nums.iter().rev().take(3).sum();
        if sum < target {
            return sum;
        }

        sum = nums[0] + nums[1] + nums[n - 1];
        let mut diff_last: i32 = sum - target;
        let mut temp: i32;
        let mut diff: i32;
        let mut left: usize;
        let mut right: usize;

        for i in 0..n - 2 {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }

            left = i + 1;
            right = n - 1;
            while right > left {
                temp = nums[left] + nums[right] + nums[i];
                diff = temp - target;
                if diff == 0 {
                    return temp;
                } else if diff > 0 {
                    right -= 1;
                    while right - 2 > left && nums[right] == nums[right - 1] {
                        right -= 1;
                    }
                } else {
                    left += 1;
                    while right - 2 > left && nums[left] == nums[left + 1] {
                        left += 1;
                    }
                }
                if diff.abs() < diff_last.abs() {
                    sum = temp;
                    diff_last = diff;
                }
            }
        }
        sum
    }

    pub fn leetcode_memory_minimun(mut nums: Vec<i32>, target: i32) -> i32 {
        let len = nums.len();
        nums.sort();
        assert!(len > 2);
        let mut res = nums[0] + nums[1] + nums[2];
        for i in 0..len - 2 {
            let mut l = i + 1;
            let mut r = len - 1;
            while l < r {
                let temp_res = nums[i] + nums[l] + nums[r];
                if temp_res == target {
                    return temp_res;
                } else if temp_res < target {
                    if target - temp_res < (res - target).abs() {
                        res = temp_res;
                    }
                    l += 1;
                } else {
                    if temp_res - target < (res - target).abs() {
                        res = temp_res;
                    }
                    r -= 1;
                }
            }
        }
        res
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    fn assert<F>(f: F)
        where F: Fn(Vec<i32>, i32) -> i32 {
        let nums = vec![3, 4, 5, 5, 7, 4, 5, 8, 0, 8, 9, -9, -8, -5, -5];
        assert_eq!(f(nums, 11), 11);
    }

    #[bench]
    fn three_sum_closest_skip(b: &mut Bencher) {
        b.iter(|| assert(Solution::three_sum_closest_skip))
    }

    #[bench]
    fn three_sum_closest(b: &mut Bencher) { b.iter(|| assert(Solution::three_sum_closest)) }

    #[bench]
    fn leetcode_memory_minimun(b: &mut Bencher) {
        b.iter(|| assert(Solution::leetcode_memory_minimun))
    }
}