leetcode15

3Sum

问题：给出一个数组S，找出里面三个数组成a+b+c = 0,且a<b<c,并且是唯一triplets

思路：先排序，从两边逼近中间求解twoSum。最开始是从前往后匹配，发现超时了。现在复杂度在O(n^2)

vector<vector<int>> threeSum(vector<int>& num) {
//排序
std::sort(num.begin(),num.end());
vector<vector<int>> result;
int len = num.size();

for(int i=0;i<len;i++)
{
    int target = 0- num[i];
    int start = i+1, end = len - 1;
    //twoSum求解
    while(start<end)
    {
        if(num[start]+num[end]==target)
        {	
            vector<int> solution;
            solution.push_back(num[i]);
            solution.push_back(num[start]);
            solution.push_back(num[end]);
            result.push_back(solution);
            start++,end--;
            //当前一位和后一位是一样的时候，直接跳过这一层的判断
            while(start<end&&num[start]==num[start-1]) start++;
            while(start<end&&num[end] ==num[end+1]) end--;
        }
        //两边判断逼近
        else if(num[start]+num[end]<target)
            start++;
        else
            end--;
    }
    //时刻判断第一位a是否重复
    if(i<len-1)
    {
        while(num[i]==num[i+1])
            i++;
    }
}
return result;
}

3ClosestSum

问题：求三个和的最相近近似解
思路：转化成求两个和离target的最相近似解

// return the twoSumClosest sum
int twoSumClosest(vector<int> &sortedNum,int start,int target){

    int head = start , tail = sortedNum.size()-1;
    int res = 0,dis = INT_MAX;
    //依据最近距离返回res
    while(head < tail)
    {
        int tmp = sortedNum[head]+ sortedNum[tail];
        if(tmp<target)
        {
            if(target-tmp<dis)
            {
                res = tmp;
                dis = target-tmp;
            }
            head++;
            
        }
        else if(tmp > target)        {
        
            if(tmp-target<dis)
            {
                res = tmp;
                dis = tmp-target;
            }
            tail--;
        }
        else
            return target;
    }
    return res;
}

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

    int n = num.size();
    sort(num.begin(),num.end());
    int res,dis = INT_MAX;
    for(int i=0;i<n-2;i++)
    {
       int target2 = target-num[i],tmpdis;
        int tmpres = twoSumClosest(num,i+1,target2);
        // 若有更近解，更新res
        if((tmpdis = abs(tmpres-target2))<dis)
        {
            res = tmpres + num[i];
            dis = tmpdis;
            // 有一样解即刻返回
            if(res==target)
                return res;
        }
    }
    return res;
}

4Sum

问题： 4个和为target
思路：2+2的方法，遍历前两个，然后求解twoSum问题

vector<vector<int> > fourSum(vector<int> &num, int target) {
    int n = num.size();
    vector<vector<int> > res;
    sort(num.begin(), num.end());
    for(int i = 0; i < n-3; i++)
    {
        if(i > 0 && num[i] == num[i-1])continue;//防止第一个元素重复
        for(int j = i+1; j < n-2; j++)
        {
            if(j > i+1 && num[j] == num[j-1])continue;//防止第二个元素重复
            int target2 = target - num[i] - num[j];
            int head = j+1, tail = n-1;
            //Two Sum Problem
            while(head < tail)
            {
                int tmp = num[head] + num[tail];
                if(tmp > target2)
                    tail--;
                else if(tmp < target2)
                    head++;
                else
                {
                    res.push_back(vector<int>{num[i], num[j], num[head], num[tail]});
                    //为了防止出现重复的二元组，使结果等于target2
                    int k = head+1;
                    while(k < tail && num[k] == num[head])k++;
                    head = k;

                    k = tail-1;
                    while(k > head && num[k] == num[tail])k--;
                    tail = k;
                }
            }
        }
    }
    return res;
}

```