leetcode18. 4Sum

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

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]
]

分析：

还是采用左右夹逼的方式，只不过又多了一层循环。不能重复控制起来比较麻烦，不如直接查找是否重复来简化。

我的代码：

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-18
//T(n)=O(n^3), S(n)=O(1)
//先排序，然后左右夹逼，最后剔除重复case
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if(nums.size() < 4) return result;
        sort(nums.begin(),nums.end());
        for(auto a = nums.begin(); a != prev(nums.end(), 3); ++a)
            for(auto b = next(a); b != prev(nums.end(), 2); ++b)
            {
                auto c = next(b);
                auto d = prev(nums.end());
                while(c < d)
                {
                    if(*a + *b + *c + *d < target)
                        ++c;
                    else if(*a + *b + *c + *d > target)
                        --d;
                    else
                    {
                        result.push_back({*a,*b,*c,*d});
                        ++c;
                        --d;
                    }
                }
            }
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(),result.end()), result.end());
        return result;
    }
};

• 有一个细节需要注意result.erase(unique(result.begin(),result.end()), result.end());这里的求值顺序会使最后那个result.end()失效吗？答案是不会。

更多利用STL的解法以后再讨论。