leetcode-16-3Sum-Closest

发表于   |  

描述

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

1
2
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

分析

其实思路和这道题是一样的，首先排序，从左到右由小到大的顺序，通过第一层循环确定第一个数，其他两个在第一个数的右边（都比第一个数大）取，两个数从两侧向中间靠拢，如果三数相加与target的差的绝对值相差比 result 更小，就更新，三数相加大于 target, 第三个数向左移动（减小）， 否则，第二个数向右移动。时间复杂度$O(n^2)$，空间复杂度是$O(1)$，因为排序是$nlogn$，查找是$O(n^2)$。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int result;
        int size = nums.size();
        
        sort(nums.begin(), nums.end());
        result = nums[0] + nums[1] + nums[size-1];
        
        for(int i = 0; i < size-1; i++) {
            int j = i + 1;
            int k = size - 1;
            
            while(j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if(abs(sum-target) <= abs(result-target)) {
                    result = sum;
                }
                
                if(sum < target) {
                    j++;
                }else if(sum == target) {
                    return result;
                }else {
                    k--;
                }
            }
        }
        return result;
    }
};

解决方案2(Rust)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
pub struct Solution {}

impl Solution {
    pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
        let mut nums = nums;
        let mut result: i32 = i32::max_value();
        nums.sort();
        let mut i = 0;
        while i < nums.len() - 2 {
            let now_min = Solution::two_sum_closest(&nums[(i+1)..nums.len()], target - nums[i]);
            if now_min.abs() < result.abs() {
                result = now_min;
                if result == 0 {
                    break;
                }
            }
            i += 1
        }
        target + result
    }

    fn two_sum_closest(nums: &[i32], target: i32) -> i32 {
        let (mut i, mut j) = (0_usize, nums.len() - 1);
        let mut result = i32::max_value();
        while i < j {
            let sum = nums[i] + nums[j];
            if sum > target {
                j -= 1;
            } else if sum < target {
                i += 1;
            } else {
                return 0;
            }
            if (sum - target).abs() < result.abs() {
                result = sum - target
            }
        }
        result
    }
}

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

    #[test]
    fn test_leetcode_16() {
        assert_eq!(Solution::three_sum_closest(vec![-1, 2, 1, -4], 1), 2);
    }
}

相关问题

(M) 3Sum Smaller
(M) 3Sum

题目来源