Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode 3Sum Closest

Leetcode algorithms 第 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.

    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).

解答

采用跟3Sum一样的思路,对数组排序,然后从头到尾遍历第一个数字,在后续子数组中寻找后两个数字,具体方法是从两边向中间扫描,如果当前和比target大,则右端左移以减小和,否则左端向右移。

由于只返回和,不需要记录取得最优值的结果。

具体代码如下:

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        int ans = -1, diff = 1 << 30; //答案,sum与target的最小距离
        for (int i = 0; i < num.size() - 2; i++) //枚举第一个数字
        {
            int j = i + 1, k = num.size() - 1;
            while (j < k) //首尾向中间扫描,寻找后两个数字
            {
                int t = num[i] + num[j] + num[k], tdiff;
                if (t > target) k--, tdiff = t - target; //大于target,减小
                else j++, tdiff = target - t;            //小于target,增加
                if (tdiff < diff) diff = tdiff, ans = t; //比最小距离还小,更新
            }
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论