4Sum – Find Unique Quadruplets that Sum to Target using O(

  • 时间：2020-09-21 09:15:21
  • 分类：网络文摘
  • 阅读：128 次

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
2
3
4
5

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Previously, we have talked about Two Sum and Three Sum. The Four Sum problem is similar.

Four Sum Algorithm using Four Pointers

First, we have to sort the array, so that we can easily skip the duplicates for the same pointer and apply the four pointer algorithm. We first iterate with O(N^2) for i and j pairs (where j is always larger than i). Then we can apply two pointer in the part that is beyond pointer j – moving towards each other until they meet in the middle.

When we find a unique quadruplet, we have to skip the duplicates by moving the last two pointer:

1
2

while (nums[k] == nums[k - 1] && (k < u)) k ++;
while (nums[u] == nums[u + 1] && (k < u)) u --;
while (nums[k] == nums[k - 1] && (k < u)) k ++;
while (nums[u] == nums[u + 1] && (k < u)) u --;

The overall algorithm complexity is O(N^3).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> r;
        if (nums.empty()) return r;        
        sort(begin(nums), end(nums));
        int n = nums.size();
        for (int i = 0; i < n; ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue;  // skip duplicates
            for (int j = i + 1; j < n; ++ j) {
                if ((j > i + 1) && (nums[j] == nums[j - 1])) continue;  // skip duplicates
                int k = j + 1;
                int u = n - 1;
                while (k < u) { // two pointer algorithm
                    int s = nums[i] + nums[j] + nums[k] + nums[u];
                    if (s == target) {
                        r.push_back({nums[i], nums[j], nums[k], nums[u]});
                        k ++;
                        u --;
                        while (nums[k] == nums[k - 1] && (k < u)) k ++; // skip duplicates
                        while (nums[u] == nums[u + 1] && (k < u)) u --; // skip duplicates
                    } else if (s > target) {
                        u --;
                    } else {
                        k ++;
                    }
                }
            }
        }
        return r;
    }
};
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> r;
        if (nums.empty()) return r;        
        sort(begin(nums), end(nums));
        int n = nums.size();
        for (int i = 0; i < n; ++ i) {
            if ((i > 0) && (nums[i] == nums[i - 1])) continue;  // skip duplicates
            for (int j = i + 1; j < n; ++ j) {
                if ((j > i + 1) && (nums[j] == nums[j - 1])) continue;  // skip duplicates
                int k = j + 1;
                int u = n - 1;
                while (k < u) { // two pointer algorithm
                    int s = nums[i] + nums[j] + nums[k] + nums[u];
                    if (s == target) {
                        r.push_back({nums[i], nums[j], nums[k], nums[u]});
                        k ++;
                        u --;
                        while (nums[k] == nums[k - 1] && (k < u)) k ++; // skip duplicates
                        while (nums[u] == nums[u + 1] && (k < u)) u --; // skip duplicates
                    } else if (s > target) {
                        u --;
                    } else {
                        k ++;
                    }
                }
            }
        }
        return r;
    }
};

The above C++ implements the solution to find the unique quadruplets that sum up to a target (4sum or four sum problem).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
江苏卫视直播-江苏卫视在线直播观看「高清」　 浙江卫视直播-浙江卫视在线直播观看「高清」　 河南卫视在线直播-河南卫视直播在线观看「高清」　 北京卫视直播-北京卫视在线直播观看「高清」　 天津卫视直播-天津卫视在线直播观看「高清」　 安徽卫视直播-安徽卫视在线直播观看「高清」　 湖北卫视直播-湖北卫视在线直播观看「高清」　 河北卫视直播-河北卫视在线直播观看「高清」　 山西卫视直播-山西卫视在线直播观看「高清」　 山东卫视直播-山东卫视在线直播观看「高清」　
评论列表
添加评论