MENU

LeetCode18. 4Sum(对撞指针)

2019 年 02 月 16 日 • 阅读: 911 • LeetCode阅读设置

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 SubmittedStatusRuntimeMemoryLanguage
a few seconds agoAccepted16 ms(剪枝)10.7 MBcpp
12 minutes agoAccepted52 ms10.7 MBcpp
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日 星期六