LeetCode #18 – 4Sum [双指针]

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

题目:

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, abcd)
  • The solution set must not contain duplicate quadruplets.

题意:给定一个数组和一个目标,求所有四个数之和为这个目标的组合。

分析:类似于3sum,先排序,两层循环枚举前两个数,双指针得到后两个数,注意判断时要去重。

代码:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if(nums.size() < 4) return res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size()-3; ++i) {
            if(i && nums[i]==nums[i-1]) continue;
            for(int j = i + 1; j < nums.size()-2; ++j) {
                if(j != i+1 && nums[j]==nums[j-1]) continue;
                int sum = target - (nums[i]+nums[j]);
                int l = j + 1, r = nums.size()-1;
                while (l < r) {
                    if(l != j+1 && nums[l]==nums[l-1]) ++l;
                    else if(r != nums.size()-1 && nums[r]==nums[r+1]) --r;
                    else if(nums[l] + nums[r] < sum) ++l;
                    else if(nums[l] + nums[r] > sum) --r;
                    else {
                        vector<int> t = {nums[i], nums[j], nums[l], nums[r]};
                        res.push_back(t);
                        ++l, --r;
                    }
                }
            }
        }
        return res;
    }
};

欢迎留言