[LeetCode]3Sum Closest

看到此文,是否觉得体内洪荒之力爆发,饥渴难耐想吐槽、情不自禁想捐赠
本文为原创文章,尊重辛勤劳动,可以免费摘要、推荐或聚合,亦可完整转载,但完整转载需要标明原出处,违者必究。

支付宝微  信

原题

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

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路

本题目的解题思路和3Sum很像,区别在于3Sum求解的是三个数字和为target(即为0),然而3SumClosest无非就是求解三个数字和与target最近的一个状态。
很容易地可以想到,将每次求解的距离,即三个数字和与target的差值记录下来,并每次求解时进行比较,寻求最小的距离。

代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        vector<int> rs;
        int l = nums.size(), dist = 100000000;
        sort(nums.begin(), nums.end());
         
        for (int i = 0; i < l - 2; ++i) { 
            int f = i + 1, b = l - 1; 
            if (i - 1 >= 0 && nums[i] == nums[i - 1]) continue;
            while (f < b) {
               if (nums[f] + nums[b] + nums[i] - target > 0) {
                    if (abs(dist) > abs(nums[f] + nums[b] + nums[i] - target)) {
                        dist = nums[f] + nums[b] + nums[i] - target;
                    }
                    while(nums[b] == nums[--b]) {}
                } else if (nums[f] + nums[b] + nums[i] - target < 0) { if (abs(dist) > abs(nums[f] + nums[b] + nums[i] - target)) {
                        dist = nums[f] + nums[b] + nums[i] - target;
                    }
                    while(nums[f] == nums[++f]) {}
                } else {
                    return target;
                }
            }
        }
     
        return dist + target; 
    }
};

时间复杂度:O(n^2)
空间复杂度:O(n)


原题:https://leetcode.com/problems/3sum-closest/description/
文章来源:胡小旭 => [LeetCode]3Sum Closest


这是一篇原创文章,如果您觉得有价值,可以通过捐赠来支持我的创作~
捐赠者会展示在博客的某个页面,钱将会用在有价值的地方,思考中...


分类: C/C++, 技术, 算法, 编程 | 标签: , , , , , | 评论 | Permalink

发表评论

电子邮件地址不会被公开。