LeetCode 题解工作台
子数组不同元素数目的平方和 II
给你一个下标从 0 开始的整数数组 nums 。 定义 nums 一个子数组的 不同计数 值如下： 令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。…
4
题型
0
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums 。
定义 nums 一个子数组的 不同计数 值如下：
- 令
nums[i..j]表示nums中所有下标在i到j范围内的元素构成的子数组（满足0 <= i <= j < nums.length），那么我们称子数组nums[i..j]中不同值的数目为nums[i..j]的不同计数。
请你返回 nums 中所有子数组的 不同计数 的 平方 和。
由于答案可能会很大，请你将它对 109 + 7 取余 后返回。
子数组指的是一个数组里面一段连续 非空 的元素序列。
示例 1：
输入：nums = [1,2,1] 输出：15 解释：六个子数组分别为： [1]: 1 个互不相同的元素。 [2]: 1 个互不相同的元素。 [1]: 1 个互不相同的元素。 [1,2]: 2 个互不相同的元素。 [2,1]: 2 个互不相同的元素。 [1,2,1]: 2 个互不相同的元素。 所有不同计数的平方和为 12 + 12 + 12 + 22 + 22 + 22 = 15 。
示例 2：
输入：nums = [2,2] 输出：3 解释：三个子数组分别为： [2]: 1 个互不相同的元素。 [2]: 1 个互不相同的元素。 [2,2]: 1 个互不相同的元素。 所有不同计数的平方和为 12 + 12 + 12 = 3 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on using DP with either BIT or Segment Tree, generally O(n log n) due to logarithmic updates and queries per index. Space complexity is O(n) for storing last occurrences and tree structures. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if candidate recognizes the state transition for subarrays ending at each index.
- question_mark
Look for efficient use of BIT or Segment Tree instead of naive O(n^2) iteration.
- question_mark
Candidate should track last occurrence to handle repeated elements correctly.
常见陷阱
外企场景- error
Naively enumerating all subarrays leads to timeouts for large n.
- error
Forgetting to update contributions when an element repeats in a subarray.
- error
Confusing sum of distinct counts with sum of distinct elements themselves.
进阶变体
外企场景- arrow_right_alt
Compute sum of cubes instead of squares of distinct counts.
- arrow_right_alt
Only consider subarrays of length exactly k.
- arrow_right_alt
Handle multisets where duplicates increase the count differently.