离线下载
PDF版 ePub版

柯于旺 · 更新于 2018-11-28 11:00:43

4 Sum(4 个数的和)

翻译

给定一个有 n 个数字的数组 S,在 S 中是否存在元素 a,b,c 和 d 的和恰好满足 a + b + c + d = target。

找出数组中所有的不想等的这四个元素,其和等于 target。

备注:

在(a,b,c,d)中的元素必须从小到大排列。(a ≤ b ≤ c ≤ d)
其结果必须不能够重复。

例如,给定 S = {1 0 -1 0 -2 2},target = 0。
一个结果集为:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

原文

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:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
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)

代码

具体的方法和前面两道题一样,我就不再赘述了。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums,int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;

        int len = nums.size();      
        for (int current = 0; current < len - 3;current++)
        {
            for(int second = current+1;second<len-2;second++)
            {
                int front = second + 1, back = len - 1;
                while (front < back)
                {
                    if (nums[current]+nums[second] + nums[front] + nums[back]  < target)
                        front++;
                    else if (nums[current] +nums[second]+ nums[front] + nums[back] > target)
                        back--;
                    else
                    {
                        vector<int> v(4);
                        v[0]=nums[current];
                        v[1]=nums[second];
                        v[2]=nums[front];
                        v[3]=nums[back];
                        result.push_back(v);
                        do {
                            front++;
                        } while (front < back&&nums[front - 1] == nums[front]);
                        do {
                            back--;
                        } while (front < back&&nums[back + 1] == nums[back]);
                    }
                } 
                while(second < len-2&&nums[second+1]==nums[second])
                    second++;
            }                               
            while (current < len - 3 && nums[current + 1] == nums[current])
                current++;
        }                                  
        return result;
    }
};

和本道题关联密切的题目推荐:

传送门:LeetCode 15 3 Sum(3 个数的和)
传送门:LeetCode 16 3 Sum Closest(最接近的 3 个数的和)