LeetCode OJ-- 3Sum Closest

https://oj.leetcode.com/problems/3sum-closest/

给一列数和target，在这一列数中找出3个数，使其和最接近target,返回这个target。

一般思路是 n*n*n,优化的话，如下：

先给数排序，然后对第一个数进行遍历 i，第二个数为i+1,第三个数为len-1,看得出的和于target的比较。如果小于target，则第二个数下标++，如果大于target，则第三个数下标--。

class Solution {

public:

    int threeSumClosest(vector<int> &num, int target) {

        int len = num.size();

        if(len<)

            return ;

        if(len == )

            return num[]+num[]+num[];

        sort(num.begin(),num.end());

        int nearAns = num[]+num[]+num[];

        for(int i = ;i<len;i++)

        {

            int j = i+;

            if(j>len-)

                break;

            int k = len-;

            while(j<k)

            {

                int sum = num[i]+num[j]+num[k];

                if(sum == target)

                    return target;

                if(sum<target)

                {

                    if(abs(target - sum) < abs(target - nearAns))

                        nearAns = sum;

                    j++;

                }

                if(sum>target)

                {

                    if(abs(target - sum) < abs(target - nearAns))

                        nearAns = sum;

                    k--;

                }

            }

        }

        return nearAns;

    }

};

巴特西

LeetCode OJ-- 3Sum Closest

最新文章

热门文章