题目链接

点击查看【music163】

题目描述

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

示例

示例1：

输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

提示

  • 0 <= nums.length <= 200
  • -10 <= nums[i] <= 10

  • -10 <= target <= 10

    思路

    排序+双指针+剪枝

    本题与0015-三数之和类似，同样可以使用双指针。但要多加一层循环，复杂度为0018-四数之和 - 图1，很有可能超时，因此我们需要进行剪枝：

  • nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target，剩下的3个数无论取什么值，其和一定大于target，直接返回最终结果

  • nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target，当前值就算与最大的3个数相加都会小于target，因此直接进行下一个循环
  • nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target，剩下的2个数无论取什么值，其和一定大于target，退出第二层循环
  • nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target，当前值就算与最大的2个数相加都会小于target，因此直接进行下一个循环

注：在测试样例中有一组为： [1000000000,1000000000,1000000000,1000000000]> 0

这样会导致int类型溢出，因此在判断的时候我们可以强制类型转换为long，也可以对该测试样例进行特判。

另：

也许可以使用回溯+剪枝，但剪枝不够狠的话可能导致超时

题解

  1. class Solution {
  2.    public:
  3.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
  4.         int n = nums.size();
  5.         if (n < 4) {
  6.             return {};
  7.         }
  8.         vector<vector<int>> ans;
  9.         sort(nums.begin(), nums.end());
  10.         for (int i = 0; i < n - 3; ++i) {
  11.             long temp = 0;
  12.             if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
  13.                 // 防止溢出
  14.                 return ans;
  15.             }
  16.             if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
  17.                 continue;
  18.             }
  19.             if (i > 0 && nums[i - 1] == nums[i]) {
  20.                 continue;
  21.             }
  22.             for (int j = i + 1; j < n - 2; ++j) {
  23.                 if (j > i + 1 && nums[j - 1] == nums[j]) {
  24.                     continue;
  25.                 }
  26.                 if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
  27.                     break;
  28.                 }
  29.                 if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
  30.                     continue;
  31.                 }
  32.                 int left = j + 1, right = n - 1;
  33.                 while (left < right) {
  34.                     int sum = nums[i] + nums[j] + nums[left] + nums[right];
  35.                     if (sum > target) {  //和太大，移动右指针
  36.                         --right;
  37.                     } else if (sum < target) {
  38.                         ++left;
  39.                     } else {
  40.                         ans.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
  41.                         ++left;
  42.                         --right;
  43.                         while (left < right && nums[left - 1] == nums[left]) {
  44.                             ++left;
  45.                         }
  46.                         while (left < right && nums[right + 1] == nums[right]) {
  47.                             --right;
  48.                         }
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.         return ans;
  54.     }
  55. };

复杂度分析

  • 时间复杂度：0018-四数之和 - 图2，其中排序的复杂度为0018-四数之和 - 图3
  • 空间复杂度：0018-四数之和 - 图4，此为排序的空间复杂度，如果题目要求不能在原数组上修改，那么还需要保存副本，空间复杂度变为0018-四数之和 - 图5