凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 18. 4Sum

分类:algorithm| 发布时间:2016-07-04 22:45:00


题目

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: The solution set must not contain duplicate quadruplets.

For example, given array S = [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]
]

题意

给出一个数组找出任意四个元素相加等于 target。 找出所有情况,注意结果集不能有重复的元组。

解法

本题的解法和 3Sum 一样不过要增加复杂度,3Sum 中较好的解法的复杂度是 O(n^2) 而这道题的解法的复杂度为 O(n^3)。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int> > ret;
        sort(nums.begin(), nums.end());
        vector<int> triplet;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); ++j) {
                int target2 = target - nums[i] - nums[j];
                int front = j + 1;
                int back = nums.size() - 1;
                while (front < back) {
                    int sum = nums[front] + nums[back];
                    if (sum < target2) {
                        front++;
                    } else if (sum > target2) {
                        back--;
                    } else {
                        triplet = { nums[i], nums[j], nums[front], nums[back] };
                        ret.push_back(triplet);
                        while (front < back && nums[front] == triplet[2]) front++;
                        while (front < back && nums[back] == triplet[3]) back--;
                    }
                }

                while (j + 1 < nums.size() && nums[j + 1] == nums[j]) j++;
            }

            while (i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;
        }

        return ret;
    }
};

通过一些检测可以最大限度减少循环次数

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int> > ret;
        sort(nums.begin(), nums.end());
        const int size = nums.size();
        vector<int> triplet;
        for (int i = 0; i < size - 3; i++) {
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
            if (nums[i] + nums[size - 3] + nums[size - 2] + nums[size - 1] < target) continue;
            for (int j = i + 1; j < size - 2; ++j) {
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                if (nums[i] + nums[j] + nums[size - 2] + nums[size - 1] < target) continue;
                int front = j + 1;
                int back = size - 1;
                while (front < back) {
                    int sum = nums[i] + nums[j] + nums[front] + nums[back];
                    if (sum < target) {
                        front++;
                    } else if (sum > target) {
                        back--;
                    } else {
                        triplet = { nums[i], nums[j], nums[front], nums[back] };
                        ret.push_back(triplet);
                        while (front < back && nums[front] == triplet[2]) front++;
                        while (front < back && nums[back] == triplet[3]) back--;
                    }
                }

                while (j + 1 < size && nums[j + 1] == nums[j]) j++;
            }

            while (i + 1 < size && nums[i + 1] == nums[i]) i++;
        }

        return ret;
    }
};

这个解法的关键在于最外层循环的:

if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
if (nums[i] + nums[size - 3] + nums[size - 2] + nums[size - 1] < target) continue;

以及次外层循环的:

if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
if (nums[i] + nums[j] + nums[size - 2] + nums[size - 1] < target) continue;