[Leetcode 18] 四数之和

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):
  • 0 <= a, b, c, d < n
  • abc 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
 
示例 1:
示例 2:
 

解法一:排序 + 双指针

  1. 将数组排序,因为后面要用双指针,且排序之后重复值会连在一起,可以很轻松地跳过重复项,不会出现重复解。
  1. 用两个嵌套循环固定前两个数字 nums[i] 和 nums[j]
    1. 跳过重复,防止生成重复的四元组。
  1. 双指针搜索另外两个数 (TwoSum)
    1. 对于区间 (j+1, n-1) 使用两个指针 k 和 l
      • 若和小于目标,左指针右移
      • 若和大于目标,右指针左移
      • 若和等于目标,记录结果,并跳过重复元素继续
  • 时间复杂度:O(n^3) 三层循环(两层固定 + 一层双指针)
  • 空间复杂度:O(1) (不计结果存储)
 
 

解法二:排序 + 哈希

和上面的 kSum 主体部分是一样的,区别在 不用双指针解决 twoSum,而是采用 单循环 + 哈希集合 的方法。
虽然哈希实现 twoSum 不需要排序,但我们需要排序来跳过重复值。
 

扩展:k-sum

先排序,再按 kSum → (k−1)Sum → ... → 2Sum 递归拆解
  • 如果现在要求 4Sum,你就先固定一个数,然后递归解决 3Sum
  • 如果要求 3Sum,那就再固定一个数,然后递归解决 2Sum
  • 最后到 2Sum,可以用双指针来求解。
复杂度
  • 时间:O(n^(k−1))
    • 排序是 O(n log n)
    • 双指针 twoSum 的复杂度是 O(n)
    • 外层的 k−2 层循环
    • 总时间复杂度为 排序 + k−2 层循环 + 1 层 twoSum
  • 空间:O(k) 递归栈
 
上一篇
[Leetcode 17] 电话号码的字母组合
下一篇
[Leetcode 19] 删除链表的倒数第 N 个节点