LeetCode 题解工作台
统计特殊四元组
给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ： nums[a] + nums[b] + nums[c] == nums[d] ，且 a 示例 1： 输入： nums = [1,2,3,6] 输出： 1 解释： 满足要求的唯…
3
题型
4
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
class Solution: def countQuadruplets(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：
nums[a] + nums[b] + nums[c] == nums[d]，且a < b < c < d
示例 1：
输入：nums = [1,2,3,6] 输出：1 解释：满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。
示例 2：
输入：nums = [3,3,6,4,5] 输出：0 解释：[3,3,6,4,5] 中不存在满足要求的四元组。
示例 3：
输入：nums = [1,1,1,3,5] 输出：4 解释：满足要求的 4 个四元组如下： - (0, 1, 2, 3): 1 + 1 + 1 == 3 - (0, 1, 3, 4): 1 + 1 + 3 == 5 - (0, 2, 3, 4): 1 + 1 + 3 == 5 - (1, 2, 3, 4): 1 + 1 + 3 == 5
提示：
4 <= nums.length <= 501 <= nums[i] <= 100
解题思路
方法一
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
ans, n = 0, len(nums)
for a in range(n - 3):
for b in range(a + 1, n - 2):
for c in range(b + 1, n - 1):
for d in range(c + 1, n):
if nums[a] + nums[b] + nums[c] == nums[d]:
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity ranges from O(n^3) with hash optimization to O(n^4) for pure brute force. Space complexity is O(n) for hash map storage. Small array size allows these approaches to run efficiently. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect questions on handling duplicate numbers in quadruplets.
- question_mark
They may probe if you can reduce four nested loops using a hash table.
- question_mark
Look for awareness of early pruning opportunities to speed up array scans.
常见陷阱
外企场景- error
Counting quadruplets incorrectly when indices are not strictly increasing.
- error
Failing to use hash lookup and iterating unnecessarily over d multiple times.
- error
Overlooking array length constraints and optimizing prematurely for larger n.
进阶变体
外企场景- arrow_right_alt
Count quadruplets where nums[a] * nums[b] * nums[c] equals nums[d].
- arrow_right_alt
Find quadruplets with any sum equal to a target value instead of the fourth element.
- arrow_right_alt
Return indices of quadruplets instead of just counting them.