LeetCode18：4Sum

全栈程序员-站长 • 2022年1月17日下午7:00 • 未分类 • 阅读 36

大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。

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)

这是求四个数的和的问题。能够和前面三个数和的问题一样转化成两个数和的问题。即先固定第一个数。再依据第一个数固定第二个数，然后就是求两数和的问题了。数组里面的元素可能会有反复元素，所以须要注意消除反复的推断。时间复杂度是O(N^3)。

runtime:192ms

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());
        vector<int>::iterator iter1=nums.begin();
        vector<int>::iterator iter2=iter1+1;

        //最外层第一个指针遍历
        for(;iter1!=nums.end()-3;iter1++)
        {

            //固定第一个指针后第二个指针遍历
            for(iter2=iter1+1;iter2!=nums.end()-2;iter2++)
            {

                //内层两个指针从两个方向遍历，这是经典的求两个数的和的问题
                int base=*iter1+*iter2;
                vector<int>::iterator iter3=iter2+1;
                vector<int>::iterator iter4=nums.end()-1;
                while(iter3<iter4)
                {
                    if((*iter3+*iter4+base)<target)
                    {
                        iter3++;
                    }
                    else if((*iter3+*iter4+base)>target)
                    {
                        iter4--;
                    }
                    else
                    {
                        //这里须要注意vector中push_back和用下标訪问的差别，用小标訪问时相似于数组，所以tmp初始化时须要指定vector的大小，可是用push_back时不要指定大小。否则小心push_back是在你指定大小的vector后加入元素
                        vector<int> tmp;
                        tmp.push_back(*iter1);
                        tmp.push_back(*iter2);
                        tmp.push_back(*iter3);
                        tmp.push_back(*iter4);
                        result.push_back(tmp);

                        //这是推断是否有反复的方式，假设下一指针依旧小于iter4而且下一个指针指向的值与当前值同样。iter3须要加1
                        while((iter3+1)<iter4 && *(iter3)==*(iter3+1)) iter3++;

                        while(iter3<(iter4-1)&& *(iter4)==*(iter4-1)) iter4--;

                        //推断完毕后还须要将iter3加1或iter4减一以继续查寻下一个和为常数的组合
                        iter3++;
                    }
                }

                //对于iter2也须要推断是否存在反复元素问题
                while(((iter2+1)!=(nums.end()-2))&&(*(iter2)==*(iter2+1))) iter2++;

            }

            //同理对于ier1也是如此
            while(((iter1+1)!=(nums.end()-3))&&(*(iter1)==*(iter1+1))) iter1++;

        }
          return result;   
    }
};