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
a、b、c和d互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
示例 2:
解法一:排序 + 双指针
- 将数组排序,因为后面要用双指针,且排序之后重复值会连在一起,可以很轻松地跳过重复项,不会出现重复解。
- 用两个嵌套循环固定前两个数字
nums[i]和nums[j]。
跳过重复,防止生成重复的四元组。
- 双指针搜索另外两个数 (TwoSum)
- 若和小于目标,左指针右移
- 若和大于目标,右指针左移
- 若和等于目标,记录结果,并跳过重复元素继续
对于区间
(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) 递归栈
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-18-四数之和
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 17] 电话号码的字母组合
下一篇
[Leetcode 19] 删除链表的倒数第 N 个节点