LeetCode刷题笔记（4Sum）

这道题本来昨天就做完了，但由于昨天要主持支部组织生活会，所以才拖到了今天，下面来分享一下经验吧！

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

题意分析：

给定一个包含n个整数的nums数组（数组没有特殊指明，应该可以为空集），请计算有多少组四元组合之和为target，找出所有的唯一组合。注：解的集合中不应包含重复的组合。

解答如下：

方法一（对撞“指针”法）

先对向量进行排序，然后用第一个for循环固定向量中最左边第一个数nums[0]，嵌套第二个for循环固定nums[1]，再将其余两个数的之和(target-nums[0]-nums[1])看成一个数(sum)，紧接着用对撞“指针”的方式，从排除了固定数的向量的两端进行扫描，若遇到两指针所指元素之和为sum则分别存下这两个数。最后用两层for循环依次固定每两个元素，执行相同操作，直到倒数第三、四个数即可。

class Solution{
public:
    vector<vector<int> > fourSum(vector<int> & nums, int target){
        vector<vector<int> > result;
        vector<int> cur(4);
        sort(nums.begin(), nums.end());
        int sum = 0;
        int len =  (int) nums.size();
        if (len < 4)
            return result;
        for (int i = 0; i < len - 3; i++) {
            cur[0] = nums[i];
            for (int j = i + 1; j < len - 2; j++) {
                cur[1] = nums[j];
                sum = target - nums[i] - nums[j];
                for (int  l= j + 1, r = len - 1; l < r; ) {
                    if ( nums[l] + nums[r] == sum){
                        cur[2] = nums[l++];
                        cur[3] = nums[r--];
                        result.push_back(cur);
                        while(l < r && nums[l] == nums[l-1] ) l++;    //为了避免出现重复解
                        while(l < r && nums[r] == nums[r+1])  r--;    //为了避免出现重复解
                    }
                    else if( nums[l] + nums[r] < sum )
                        l++;
                    else
                        r--;
                }
                while(j < len - 2 && nums[j] == nums[j+1])  j++; //为了避免出现重复解
            }
            while(i < len - 3 && nums[i] == nums[i+1])  i++;     //为了避免出现重复解
        }
        return result;
    }
};

提交后的结果如下：

LeetCode刷题笔记（4Sum）

方法二（优化方法一）

①用continue来提前结束不必要的循环。②对于二维向量的赋值，应先创建一个定长的一维向量，然后对一维向量用push_back方法进行挨个存储，最后二维向量用push_back方法把一维向量挨个存储下来。③当for循环的第三个表达式为空时，一般可以改写成while循环。④tmp.clear();用于清理缓存。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        int len = nums.size();
        if (len < 4)
            return result;
        vector<int> tmp;
        sort(nums.begin(),nums.end());
        for (int i = 0; i < len-3; i ++)
        {
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            for (int j = i+1; j < len-2; j ++)
            {
                if (j > i+1 && nums[j] == nums[j-1])
                    continue;
                int l = j+1;
                int r = len-1;
                while (l < r)
                {
                    if (nums[i]+nums[j]+nums[l]+nums[r] < target)
                        l++;
                    else if (nums[i]+nums[j]+nums[l]+nums[r] > target)
                        r--;
                    else
                    {
                        tmp.clear(); //清理缓存
                        tmp.push_back(nums[i]);
                        tmp.push_back(nums[j]);
                        tmp.push_back(nums[l]);
                        tmp.push_back(nums[r]);
                        result.push_back(tmp);
                        l++;
                        r--;
                        while (l < r && nums[l] == nums[l-1])
                            l++;
                        while (l < r && nums[r] == nums[r+1])
                            r--;
                    }
                }
            }
        }
        return result;
    }
};

提交后的结果如下：

LeetCode刷题笔记（4Sum）

日积月累，与君共进，增增小结，未完待续。

LeetCode刷题笔记（4Sum）

相关推荐