LeetCode 算法题 18. 四数之和

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

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解法

本题的解法和 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;

凌云的博客

行胜于言

LeetCode 算法题 18. 四数之和

题目

解法