Leetcode——18.4Sum

1. 概述

1.1 题目

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

1.2 解题思路

这道题中需要的是在一个数组中需找四个数字使得他们的和等于目标值。这道题相比于之前的3Sum问题其实是一样的，我们可以套用3Sum的思路来解题。这里可以将目标值减去第一个数，那么这样的情况就变成了3Sum问题了。

2.  编码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int len(nums.size());
        vector<vector<int>> value;
        sort(nums.begin(), nums.end());
        if(len < 4) return value;
        if(nums[0]==nums[len-1] && 4==len && target==nums[0]*4)
        {
            value.push_back(nums);
            return value;
        }
        
        int left(0), right(0);
        for(int i=0; i<len-3; ++i)  //这里的上限是len-3是因为有4个数，最后一组情况的起始地址是len-4
        {
            if(i>0 && nums[i]==nums[i-1]) continue;
            for(int k=i+1; k<len-2; ++k)
            {
                if(k>i+1 && nums[k]==nums[k-1]) continue;
                int temp = target - nums[i] - nums[k];
                int left = k+1;
                int right = len-1;
                while(left<right)
                {
                    int m = temp - nums[left] -nums[right];
                    if(0 == m)
                    {
                        vector<int> n(4,0);
                        n[0] = nums[i]; n[1] = nums[k]; n[2] = nums[left]; n[3] = nums[right];
                        value.push_back(n);
                        while(left<right && nums[left]==nums[left+1]) ++left;
                        while(left<right && nums[right]==nums[right-1]) --right;
                        --right;
                        ++left;
                    }
                    else if(0 < m)
                        ++left;
                    else
                        --right;
                }
            }
        }
        return value;
    }
};