LeetCode18. 4Sum（对撞指针）

Medium
Accepted：208,336
Submissions：705,834

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

链接

https://leetcode.com/problems/4sum/

题意

给定一个包含n个元素的数组nums和一个整数target，找到nums中所有不同的四元组（a/b/c/d）使得a+b+c+d=target，不同指四元组中的四个值不完全相同。和之前的题LeetCode15. 3Sum（对撞指针）类似。

题解

首先两重循环找到两个数nums[i]和nums[j]，然后再使用对撞指针得到nums[l]和nums[r]使得nums[i] + nums[j] + nums[l] + nums[r]==target，思路和3Sum一样。
时间复杂度$O(n^3)$，还可以在循环的过程中进行“剪枝”。

代码

Time Submitted	Status	Runtime	Memory	Language
a few seconds ago	Accepted	16 ms（剪枝）	10.7 MB	cpp
12 minutes ago	Accepted	52 ms	10.7 MB	cpp

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 3; ++i)
        {
            if (i > 0 && nums[i] == nums[i-1]) // 后面一个元素与前面一个元素相同时，找到的四元组一样
                continue;
            if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) // 剪枝 当前元素加上最小三个
                break;
            if (nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target) // 当前元素加上最大三个
                continue;
            for (int j = i + 1; j < n - 2; ++j)
            {
                if (j > i + 1 && nums[j] == nums[j-1]) // 后面一个元素与前面一个元素相同时，找到的四元组一样
                    continue;
                if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) // 剪枝
                    break;
                if (nums[i] + nums[j] + nums[n-1] + nums[n-2] < target)
                    continue;
                int l = j + 1, r = n - 1;
                while (l < r)
                {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum > target)
                        r--;
                    else if (sum < target)
                        l++;
                    else // 找到
                    {
                        ans.push_back({nums[i], nums[j], nums[l], nums[r]});
                        while (l < r && nums[l+1] == nums[l]) // 相同元素左指针右移
                            ++l;
                        while (l < r && nums[r-1] == nums[r]) // 右指针左移
                            --r;
                        ++l, --r;
                    }
                }
            }
        }
        return ans;
    }
};

The end.
2019年2月16日星期六