LeetCode 18 4Sum (Tag:Array Difficulty:Medium)

前言

关于 LeetCode 数组类型题目的相关解法，可见LeetCode 数组类型题目做前必看，分类别解法总结了题目，可以用来单项提高。觉得有帮助的话，记得多多点赞关注哦，感谢！

题目描述

给定一个包含 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]]

示例 2：
输入：nums = [], target = 0
输出：[]

链接：leetcode-cn.com/problems/4s…

题解

暴力解法，四层循环，并去重，时间复杂度为 O(n4)
双层循环后加双指针减少时间复杂度，同时事先排序，用于去重，见代码，时间复杂度 O(n³)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    if (nums.length < 4) return []
    nums.sort((a,b) => a - b)
    const n = nums.length
    let res = []
    for (let i = 0 ; i < n - 3; ++i) {
      if (i > 0 && nums[i] === nums[i-1]) continue  // 去重
      for (let j = i + 1; j < n - 2; ++j) {
        if (j > i + 1 && nums[j] === nums[j-1]) continue // 去重
        let l = j + 1
        let r = n - 1
        const leave = target - nums[i] - nums[j]
        while (l < r) {
          if (nums[l] + nums[r] === leave) {
            res.push([nums[i], nums[j], nums[l], nums[r]])
            while (l < r && nums[l] === nums[l+1]) ++l // 去重
            while (l < r && nums[r] === nums[r-1]) --r // 去重
            ++l
            --r
          } else if (nums[l] + nums[r] > leave) {
            --r
          } else {
            ++l
          }
        }
      }
    }
  return res
};

常见问题FAQ

免费下载或者VIP会员专享资源能否直接商用？: 本站所有资源版权均属于原作者所有，这里所提供资源均只能用于参考学习用，请勿直接商用。若由于商用引起版权纠纷，一切责任均由使用者承担。更多说明请参考 VIP介绍。

提示下载完但解压或打开不了？: 最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量，若小于网盘提示的容量则是这个原因。这是浏览器下载的bug，建议用百度网盘软件或迅雷下载。若排除这种情况，可在对应资源底部留言，或联络我们.。

找不到素材资源介绍文章里的示例图片？: 对于PPT，KEY，Mockups，APP，网页模版等类型的素材，文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买，且本站不负责(也没有办法)找到出处。同样地一些字体文件也是这种情况，但部分素材会在素材包内有一份字体下载链接清单。