OJ练习49——T16 3Sum Closest

找一个序列中三个数，其和与给定的target最接近。

【思路】

还是练习48中总结的，将题目变成2sum。

【my code】

int threeSumClosest(vector<int>& num, int target) {
        int result=0;
        int sub=INT_MAX;
        int n=num.size();
        sort(num.begin(),num.end());
        for(int i=0; i<n; i++)
        {
            int j=i+1, k=n-1;
            while(j<k){
                int cur=num[i]+num[j]+num[k];
                if(cur<target){
                    j++;
                    if(target-cur<sub){
                        sub=target-cur;
                        result=cur;
                    }
                }
                else if(cur>target){
                    k--;
                    if(cur-target<sub){
                        sub=cur-target;
                        result=cur;
                    }
                }
                else{
                    sub=0;
                    result=cur;
                    break;
                }
            }
        }
        return result;
    }

注意临时变量和最终结果的存储。即result、sub、cur在什么时候赋值保存。

虽然是现学现卖，也是值得鼓励的。