标签：数组、中等难度

问题描述

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.

给定整数数组nums和目标值target,判断数组中是否存在元素a,b,c和d使得a+b+c+d=target? 给定目标值target寻找所有的四元组，使得其和为target。
注意: 解集合中不包含重复的四元组。

示例：
给定数组nums = [1, 0, -1, 0, -2, 2], 和目标值target = 0.
解集合是：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

解决方法

方法1：暴力破解法

任选四个元素，判断其值是否为target。
但这里存在一个问题，如果两个解相同，则仅保存一个解，因为题目中要求解集合中不包含重复的四元组。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        vector<int> res;
        for(int i = 0; i < nums.size() - 3; i++) {
            for(int j = i + 1; j < nums.size() - 2; j++) {
                for(int k = j + 1; j < nums.size() - 1; k++) {
                    for(int m = k + 1; k < nums.size(); m++) {
                        if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
                            bool found = false;
                            res.clear();
                            res.push_back(i);
                            res.push_back(j);
                            res.push_back(k);
                            res.push_back(m);
                            for(int n = 0; n < result.size(); n++) {
                                if (result[i] == res) {
                                    found = true;
                                    break;
                                }
                            }
                            if (found == false)
                                result.push_back(res);
                        }
                    }
                }
            }
        }
        return result;
    }
};

算法分析：

• 程序中包含5层for循环，时间复杂度接近O(n⁵)。
• 运行时间：Time Limit Exceeded

方法二：排序法

首先对数组进行排序，接着任选两个数i和j。然后，从两端遍历数组，寻找其和值等于target的端点k和m。由于数组有序，假设A[i]+A[j]+A[k]+A[m]小于target，则将k右移；若其和大于target，则将m左移。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if(nums.size() < 4)
            return result;
        
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 3; i++) {
            for(int j = i + 1; j < nums.size() - 2; j++) {
                int k = j + 1;
                int m = nums.size() - 1;
                while (k < m) {
                    if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
                        bool found = false;
                        vector<int> res;
                        res.push_back(nums[i]);
                        res.push_back(nums[j]);
                        res.push_back(nums[k]);
                        res.push_back(nums[m]);
                        for(int n = 0; n < result.size(); n++) {
                            int equal = 0;
                            for(int p = 0; p < res.size(); p++) {
                                if(result[n][p] == res[p]) {
                                    equal++;
                                } else {
                                    break;
                                }
                            }
                            if (equal == 4)found = true;
                        }
                        if (found == false) {
                            result.push_back(res);
                        }
                    }
                    if(nums[i] + nums[j] + nums[k] + nums[m] < target)
                        k++;
                    else
                        m--;
                }
            }
        }
        return result;
    }
};

算法分析

• 运行时间：72ms

方法三：

对方法二做了一些优化，避免重复元素。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if(nums.size() < 4)
            return result;
        
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 3; i++) {
            if(i > 0 && 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 k = j + 1;
                int m = nums.size() - 1;
                while (k < m) {
                    if (nums[i] + nums[j] + nums[k] + nums[m] == target) {
                        vector<int> res;
                        res.push_back(nums[i]);
                        res.push_back(nums[j]);
                        res.push_back(nums[k]);
                        res.push_back(nums[m]);
                        
                        result.push_back(res);
                        while (k < m && nums[k++] == nums[k]) {}
                        while (k < m && nums[m--] == nums[m]) {}
                    }
                    else if(nums[i] + nums[j] + nums[k] + nums[m] < target) {
                        while (k < m && nums[k++] == nums[k]) {}
                    }
                    else
                        while (k < m && nums[m--] == nums[m]) {};
                }
            }
        }
        return result;
    }
};

算法分析

• 时间复杂度约为O(n³)
• 运行时间：52ms