美文网首页程序员
16. 3Sum Closest

16. 3Sum Closest

作者: Nautilus1 | 来源:发表于2017-10-23 18:29 被阅读0次

题目描述:给定一个有n个整数的数组S,和目标值target,在S中找三个数使其和与目标值最接近。假定每个输入只有一个解。如:

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

分析:思路与3Sum类似,先排序再左右夹逼,不同之处在于因为找的是最接近目标值的3元组,故设变量记录每次三元组的和与目标值的差值,记录差值最小时的三元组的和。时间复杂度O(n^2),空间O(1)。

代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        
        int ans = 0;
        int mingap = INT_MAX;         //最小差值
        
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size() - 2; i ++)
        {
            int l = i + 1;
            int r = nums.size() - 1;
            
            while( l < r )
            {
                int s = nums[i] + nums[l] + nums[r];
                int gap = abs(s - target);
                
                if (gap < mingap)
                {
                    ans = s;
                    mingap = gap;
                }
                if (s < target)
                    l ++;
                else
                    r --;
            }
        }

        return ans;
    }
};

相关文章

  • LeetCode #16 2018-07-28

    16. 3Sum Closest Given an array nums of n integers and an...

  • Day3

    16. 3Sum Closest Given an array S of n integers, find thr...

  • LeetCode 16. 3Sum Closest

    16. 3Sum Closest Given an array S of n integers, find thr...

  • 16. 3Sum Closest

    题目: Given an array S of n integers, find three integers i...

  • 16. 3Sum Closest

    题目: 给定一个nums由n个整数和一个整数组成的数组target,找出三个整数nums,使总和最接近target...

  • 16. 3Sum Closest

    Given an array nums of n integers and an integer target, ...

  • 16. 3Sum Closest

    Description Given an array S of n integers, find three in...

  • 16. 3Sum Closest

    Given an array nums of n integers and an integer target, ...

  • 16. 3Sum Closest

    Description Given an array S of n integers, find three in...

  • 16. 3Sum Closest

    先排序,然后左右夹逼,每次当sum-target < diff 用diff记录下最小距离

网友评论

    本文标题:16. 3Sum Closest

    本文链接:https://www.haomeiwen.com/subject/kxbauxtx.html