4 Sum

LeetCode笔记 阅读(313)

编号 : 18      
难度 : <font color="orange">Medium</font>

# 题目 :  
>Given an array `nums` of n integers and an integer `target`, are there elements *a*, *b*, *c*, and *d* in `nums` 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.
>
>**Example**:
>>
>>```
>>Given array nums = [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]  
>>]  
>>```

# 解 :  
```Cpp
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        /* 排序 */
        sort(nums.begin(), nums.end());
        return findSumInSortedArray(nums, target, 4);
    }
    
    /* 采用递归来解 */
    vector<vector<int>> findSumInSortedArray(vector<int>& nums, int target, int n)
    {
        vector<vector<int>> ret;
        if(nums.size() < n)
        {
            return ret;
        }
        
        if(n == 2)
        {
            /* 从两端向内搜索 */
            int x = 0;
            int y = nums.size() - 1;
            while(x < y)
            {
                int sum = nums[x] + nums[y];
                if(nums[x] + nums[y] < target)
                {
                    for(int i = nums[x]; x < y && nums[x] == i; x++);
                }
                else if(nums[x] + nums[y] > target)
                {
                    for(int i = nums[y]; x < y && nums[y] == i; y--);
                }
                else
                {
                    vector<int> temp = {nums[x], nums[y]};
                    ret.push_back(temp);

                    /* 跳过重复 */
                    for(; x < y && nums[x] == temp[0]; x++);
                    for(; x < y && nums[y] == temp[1]; y--);
                }
            }
        }
        else
        {
            for(int x = 0; x < nums.size() - n + 1;)
            {
                /* 因为是有序的,所以必然有nums[left] * n <= SUM <= nums[right] * n  */
                if(target < nums[x] * n || target > *(nums.end()-1) * n)
                {
                    break;
                }

                /* 递归 */
                vector<int> subVector(nums.begin() + x + 1, nums.end());
                auto temp = findSumInSortedArray(subVector, target - nums[x], n-1);
                
                /* 把当前值插入子问题的结果中,并与之前的解合并 */
                for(auto& element : temp)
                {
                    element.push_back(nums[x]); // 插入
                    ret.push_back(element);     // 合并
                }
                
                /* 跳过重复 */
                for(int i = nums[x];x < nums.size() - n + 1 && nums[x] == i; x++);
                
            }
        }
        
        return ret;
    }
};
```


# 分析
这道题的解法和[第15题](/article/reading?id=36)一摸一样,通过递归,把*N个数字之和*的问题化为*N-1个数字之和*的问题;并通过将数据排序,最后两个数字采用从外侧向内搜索的方式降低一阶复杂度。

Markdown使用 帮助


匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!

匿名

爆ぜろリアル  弾けろシナプス   バニッシュメント・ディス・ワールド!

匿名

在山的那边,海的那边,有一群蓝精灵。