/// 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::*;

    fn assert<F>(f: F)
        where F: Fn(Vec<i32>, i32) -> i32 {
        let nums = vec![1, 1, 1, 0];
        assert_eq!(f(nums, -100), 2);

        let nums = vec![1, 1, 1, 0];
        assert_eq!(f(nums, 100), 3);

        let nums = vec![-1, 2, 1, -4];
        assert_eq!(f(nums, 0), -1);

        let nums = vec![1, 1, 1, 0];
        assert_eq!(f(nums, 3), 3);

        let nums = vec![-1, 2, 1, -4];
        assert_eq!(f(nums, 1), 2);

        let nums = vec![-1, 0, 1, 2, 3];
        assert_eq!(f(nums, 4), 4);

        let nums = vec![1, 2, 4, 8, 16, 32, 64, 128];
        assert_eq!(f(nums, 82), 82);

        let nums = vec![3, 4, 5, 5, 7];
        assert_eq!(f(nums, 13), 13);

        let nums = vec![3, 4, 5, 5, 7, 4, 5, 8, 0, 8, 9, -9, -8, -5, -5];
        assert_eq!(f(nums, 11), 11);

        let nums = vec![-1, 0, 1, 2, 3];
        assert_eq!(f(nums, 5), 5);
    }

    bench!(assert Solution::three_sum_closest_skip);
    bench!(assert Solution::three_sum_closest);
    bench!(assert Solution::leetcode_memory_minimun);
}