[위 에] 3Sum 3Sum 가장 가 까 운 4Sum

난이도: 3
3Sum 의 제목:
한 열 수 를 제시 하고 모든 만족 조건 의 세 개 수 를 찾 아 라. 조건: 세 개 수 를 더 하면 0 이다.
 3Sum Closest 의 제목:
한 열 수 를 제시 하고 세 개의 수 를 찾 아 세 개의 수 를 더 하면 target 에 가장 가깝다.
4Sum：
3sum 과 마찬가지 로 4 개 에 불과 합 니 다.
해법:
다 똑 같 아.기본적으로 몇 줄 을 고치 면 다른 두 문 제 를 통과 할 수 있다.
3Sum 의 해법:
작은 것 부터 큰 것 까지 순서대로 정렬 하 다
찾 은 세 개의 숫자 a, b, c 만족 을 가정 합 니 다.
a+b+c=0
a<=b<=c
왼쪽 에서 오른쪽으로 a 를 매 거 하고 [a + 1, n] 에서 b 와 c 를 찾 아 b + c = = - a
초기 명령 b = a + 1, c = n
b + c < - a 시 b + c 를 늘 리 기 위해 서 는 b 를 오른쪽으로 이동 시 켜 야 합 니 다.
b + c > - a 시 b + c 를 줄 이기 위해 c 를 왼쪽으로 이동 시 켜 야 합 니 다.
b + c = a 시 결 과 를 기록 합 니 다.
O(n^2)
3Sum

class Solution
{
public:
    vector< vector<int> > threeSum(vector<int> &num)
    {
        vector< vector<int> > ans;
        sort(num.begin(),num.end());
        for(int i=0;i<num.size();i++)
        {
            if(i-1>=0&&num[i] == num[i-1])//  num[i]  num[i-1]         
            {
                continue;
            }
            //j,k,num[j]+num[k]=-num[i]
            int j=i+1;
            int k=num.size()-1;
            while(j<num.size()&&k>i&&j<k)
            {
                if(num[j]+num[k]>-num[i])   k--;
                else if(num[j]+num[k]<-num[i])  j++;
                else
                {
                    vector<int>tmp;
                    tmp.push_back(num[i]);
                    tmp.push_back(num[j]);
                    tmp.push_back(num[k]);
                    if(ans.size()>=1&&ans[ans.size()-1][0] == num[i]&&ans[ans.size()-1][1] == num[j]&&ans[ans.size()-1][2] == num[k])
                    {
                        j++;
                        continue;
                    }
                    ans.push_back(tmp);
                    j++;
                }
            }
        }
        return ans;
    }
};

 3Sum Closest 

class Solution
{
public:
    int threeSumClosest(vector<int> &num, int target)
    {
        int ans=0x3fffffff;
        sort(num.begin(),num.end());
        for(int i=0;i<num.size();i++)
        {
            if(i-1>=0&&num[i] == num[i-1])//  num[i]  num[i-1]         
            {
                continue;
            }
            //j,k,num[i]+num[j]+num[k]=target
            int j=i+1;
            int k=num.size()-1;
            while(j<num.size()&&k>i&&j<k)
            {
                if(num[i]+num[j]+num[k]>target)   
                {
                    if(num[i]+num[j]+num[k]-target<abs(ans-target))
                    {
                        ans=num[i]+num[j]+num[k];
                    }
                    k--;
                }
                else if(num[i]+num[j]+num[k]<target)  
                {
                    if(target-num[i]-num[j]-num[k]<abs(ans-target))
                    {
                        ans=num[i]+num[j]+num[k];
                    }
                    j++;
                }
                else
                {
                    return target;
                }
            }
        }
        return ans;
    }
};

4Sum

class Solution
{
public:
    vector<vector<int> > fourSum(vector<int> &num, int target)
    {
        sort(num.begin(),num.end());
        vector<vector<int> > ans;
        for(int i=0;i<num.size();i++)
        {
            if(i>=1&&num[i] == num[i-1])
            {
                continue;
            }
            for(int j=i+1;j<num.size();j++)
            {
                if(j-1>=i+1&&num[j] == num[j-1])
                {
                    continue;
                }
                int k=j+1;
                int l=num.size()-1;
                while(k<l&&k<num.size())
                {
                    if(num[i]+num[j]+num[k]+num[l] > target)    l--;
                    else if(num[i]+num[j]+num[k]+num[l] < target)   k++;
                    else
                    {
                        if(ans.size()>0&&ans[ans.size()-1][0] == num[i]&&ans[ans.size()-1][1] == num[j]&&ans[ans.size()-1][2] == num[k]&&ans[ans.size()-1][3] == num[l])
                        {
                            k++;
                            continue;
                        }
                        vector<int>tmp;
                        tmp.push_back(num[i]);
                        tmp.push_back(num[j]);
                        tmp.push_back(num[k]);
                        tmp.push_back(num[l]);
                        ans.push_back(tmp);
                        k++;
                    }
                }
            }
        }
        return ans;
    }
};