leetcode 16. 3Sum Closest (k-sum问题,two pointer)

Posted by 111qqz on Thursday, April 13, 2017

TOC

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.

思路: 排序,然后two pointer,复杂度 O(n^2)

/* ***********************************************
Author :111qqz
Created Time :2017年04月13日 星期四 16时24分28秒
File Name :16.cpp
************************************************ */
class Solution {

public:

    int n;
    int threeSumClosest(vector<int>& nums, int target) {
    n = nums.size();
    sort(nums.begin(),nums.end());
    int mn = 0x3f3f3f3f;
    int x,y,z;
    for ( int i = 0 ; i <=n-3 ; i++)
    {
        int head = i+1;
        int tail = n-1;
        int tar = target - nums[i];
        while (head<tail)
        {
        int cur = target-nums[i]-nums[head]-nums[tail];
        if (abs(cur)<mn)
        {
            mn = abs(cur);
            x = nums[i];
            y = nums[head];
            z = nums[tail];
        }
        if (nums[head]+nums[tail]==tar) return target;
        if (nums[head]+nums[tail]<tar) head++;
        else tail--;
        }
    }
    return x + y + z;


        

    }

};

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付