two sum&&three sum&&four sum&&th

two sum

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> rec(2,-1);
        unordered_map<int,int> m;
        int n = nums.size();
        if(n<2)
          return rec;
        for(int i=0;i<n;i++)
        {
            if(m.find(target-nums[i])==m.end())
              m[nums[i]] = i;
            else
            {
                rec[0] = m[target-nums[i]];
                rec[1] = i;
            }
        }
        return rec;
    }
};

3 sum

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int n = nums.size();
        sort(nums.begin(),nums.end());
        if(n<=2)
          return result;
        
        for(int i=0;i<n-2;i++)
        {  
            int j = i+1;
            int k = n-1;
            while(j<k)
            {
                if(nums[i]+nums[j]+nums[k]==0)
                {
                   vector<int> rec;
                   rec.push_back(nums[i]);
                   rec.push_back(nums[j]);
                   rec.push_back(nums[k]);
                   result.push_back(rec);
                   j++;
                   k--;
                   while(j<k&&nums[j-1]==nums[j])//注意，此处的j加过1了
                     j++;
                   while(j<k&&nums[k+1]==nums[k])//注意，此处的k减过1了
                     k--;
                }
                else if(nums[i]+nums[j]+nums[k]<0)
                   j++;
                else 
                   k--;
            }
            while(i<n-3&&nums[i+1]==nums[i])
               i++;
        }
        return result;
    }
};

3Sum Closest

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        int last = -1;
        int minClosest = INT_MAX;
        
        for(int i=0;i<n;i++)
        {
            int j = i+1;
            int k = n-1;
            while(j<k)
            {
                int sum = nums[i]+nums[j]+nums[k];
                if(sum<target)
                  j++;
                else if(sum>target)
                  k--;
                else if(sum==target)
                {
                  j++;
                  k--;
                }
                if(abs(target-sum)<minClosest)
                {
                    minClosest = abs(target-sum);
                    last = sum;
                }
            }
        }
        return last;
    }
};

4 sum

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

利用set来实现：

3 sum

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        set<vector<int>> mSet;
        int n = nums.size();
        sort(nums.begin(),nums.end());

        if(n<=2)
          return result;
        
        for(int i=0;i<n-2;i++)
        {  
            int j = i+1;
            int k = n-1;
            while(j<k)
            {
                if(nums[i]+nums[j]+nums[k]==0)
                {
                   vector<int> rec;
                   rec.push_back(nums[i]);
                   rec.push_back(nums[j]);
                   rec.push_back(nums[k]);
                   mSet.insert(rec);
                   j++;
                   k--;
                }
                else if(nums[i]+nums[j]+nums[k]<0)
                   j++;
                else 
                   k--;
            }

        }
        return vector<vector<int>>(mSet.begin(),mSet.end()); //注意此种写法！！！
    }
};

4 sum

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        int n = nums.size();
        if(n<=3)
          return result;
        set<vector<int>> mSet;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-3;i++)
        {
            for(int j=i+1;j<n-2;j++)
            {
                int k = j+1;
                int l = n-1;
                int sum = target - nums[i] - nums[j];
                while(k<l)
                {
                    if(sum == nums[k] + nums[l])
                    {
                        vector<int> rec;
                        rec.push_back(nums[i]);
                        rec.push_back(nums[j]);
                        rec.push_back(nums[k]);
                        rec.push_back(nums[l]);
                        mSet.insert(rec);
                        k++;
                        l--;
                    }
                    else if(nums[k] + nums[l] < sum)
                    {
                        k++;   
                    }
                    else
                    {
                        l--;
                    }
                }
            }
        }
        return vector<vector<int>>(mSet.begin(),mSet.end());//注意此种写法！！！
    }
};