leecode第十六题（最接近的三数之和）

class Solution {

public:

    void quick_order(vector<int>& num, int star, int en)//快排

    {

        int start = star;

        int end = en;

        if (start >= end)

            return;

        int index = num[start];//就第一个设为阈值

        while (start < end)

        {

            while (start < end && index <= num[end])//先看右边，把第一个小于index数找出

                end--;

            int temp1 = num[start];//交换

            num[start] = num[end];

            num[end] = temp1;

            while (start < end && index >= num[start])//再看右边，把第一个大于index的数找出

                start++;

            int temp2 = num[start];//交换

            num[start] = num[end];

            num[end] = temp2;

        }

        quick_order(num, star, start-);//分左右子集迭代

        quick_order(num, start + , en);

        return;

    }

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

        int len=nums.size();

        long res=*INT_MAX;

        if(len==)//输入判断

            return ;

        int start=,end=len-;

        quick_order(nums,start,end);//快排

        for (int c = nums.size()-; c >= ; --c)

        {

            int tar=target-nums[c];//设置a和b要找的数字

            for (int a = , b = c-; a < b; )

            {

                if (abs(res)>=abs(nums[a]+nums[b]+nums[c]-target))//先检验是否更接近target

                    res=nums[a]+nums[b]+nums[c]-target;

                int tmp_sum = nums[a]+nums[b];//再进行下一步迭代

                if (tmp_sum < tar)

                    ++a;

                else

                    --b;

            }

        }

        return int(res+target);

    }

};

分析：

和上个类似，也是O（n^2）时间复杂度遍历。