Leetcode16. 3Sum Closest

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

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

我的代码：时间复杂度O(n^2)

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-16
//T(n)=O(n^2), S(n)=O(1)
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int result = 0;
        int min_gap = INT_MAX;
        //排序
        sort(nums.begin(),nums.end());
        auto vbeg = nums.begin();
        auto vend = nums.end();
        for(auto indexi = vbeg ; indexi < vend - 2; ++indexi)
        {
            auto indexj = indexi + 1;
            auto indexk = vend - 1;
            while(indexj < indexk)
            {
                auto sum = *indexi + *indexj + *indexk;
                auto gap = abs(sum - target);//绝对值
                if(gap < min_gap)
                {
                    result = sum;
                    min_gap = gap;
                }
                if(sum < target) ++indexj;
                else --indexk;
            }
        }
        return result;
    }
};

分析：和上一题类似，先排序，然后夹逼；只不过，不能使用break，需要全部遍历一遍。因为以下的代码对于本题不适用：

if(3*(*indexi) > target) break;
if(2*(*indexj) > (target - *indexi)) break;//仍然可以找abs最小值

这里容易产生一个错觉，就是如果满足if(3*(*indexi) > target)，那么最小结果一定是indexi与后面紧邻的两个数之和。然而实际其实并不是这样的。因为也可能是indexi与前面一个和后面一个之和。

• int min_gap = INT_MAX
• abs(sum - target) 绝对值
• 时间复杂度为O(n^2)，已经是最优

优秀代码：时间复杂度O(n^2)

与我的代码差不多，只不过使用了一些新的STL的接口。

class Solution
{
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        int result = 0;
        int min_gap = INT_MAX;
        sort(nums.begin(), nums.end());
        for (auto a = nums.begin(); a != prev(nums.end(), 2); ++a)
            {
                auto b = next(a);
                auto c = prev(nums.end());
                while (b < c)
                    {
                        const int sum = *a + *b + *c;
                        const int gap = abs(sum - target);
                        if (gap < min_gap)
                            {
                                result = sum;
                                min_gap = gap;
                            }
                        if (sum < target) ++b;
                        else --c;
                    }
            }
        return result;
    }
};

• next 和 prev，传入迭代器和数字n，返回向前或者向后n个位置的迭代器。默认n=1。