What is the main pattern used in Subarrays Distinct Element Sum of Squares I?

The problem follows the Array scanning plus hash lookup pattern, where a hash set tracks distinct elements efficiently.

How do I handle duplicates when computing distinct counts?

Use a hash map to maintain frequencies, ensuring each unique element is counted once per subarray.

Can this be solved faster than O(n^2)?

Sliding window and precomputed contribution approaches can reduce redundant counting, potentially improving practical performance.

What is the expected output for nums = [1,2,1]?

The sum of squares of distinct counts for all subarrays is 15, calculated from [1], [2], [1], [1,2], [2,1], [1,2,1].

Why use a hash set instead of a simple array for tracking?

A hash set dynamically handles distinct element presence regardless of values and avoids manual counting or index mapping.

#2913

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

子数组不同元素数目的平方和 I

给你一个下标从 0 开始的整数数组 nums 。定义 nums 一个子数组的不同计数值如下：令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。…

数组哈希表

题目描述

给你一个下标从 0 开始的整数数组 nums 。

定义 nums 一个子数组的 不同计数 值如下：

令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。

请你返回 nums 中所有子数组的 不同计数 的平方和。

由于答案可能会很大，请你将它对 10⁹ + 7 取余后返回。

子数组指的是一个数组里面一段连续非空的元素序列。

示例 1：

输入：nums = [1,2,1]
输出：15
解释：六个子数组分别为：
[1]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[1]: 1 个互不相同的元素。
[1,2]: 2 个互不相同的元素。
[2,1]: 2 个互不相同的元素。
[1,2,1]: 2 个互不相同的元素。
所有不同计数的平方和为 1² + 1² + 1² + 2² + 2² + 2² = 15 。

示例 2：

输入：nums = [2,2]
输出：3
解释：三个子数组分别为：
[2]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[2,2]: 1 个互不相同的元素。
所有不同计数的平方和为 1² + 1² + 1² = 3 。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

lightbulb

解题思路

方法一：枚举

我们可以枚举子数组的左端点下标 $i$ ，对于每个 $i$ ，我们在 $[i, n)$ 的范围内枚举子数组的右端点下标 $j$ ，并统计 $nums[j]$ 的值，将其加入到集合 $s$ 中，记 $s$ 的大小为 $cnt$ ，那么 $nums[i..j]$ 的不同计数为 $cnt$ ，将其平方后加入到答案中。

枚举结束后，返回答案即可。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i in range(n):
            s = set()
            for j in range(i, n):
                s.add(nums[j])
                ans += len(s) * len(s)
        return ans

speed

复杂度分析

指标	值
时间	complexity ranges from O(n^2) for brute-force to O(n)–O(n^2) depending on sliding window optimizations. Space complexity is O(n) for hash sets or hash maps used to track distinct elements.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about counting distinct elements efficiently within subarrays.
question_mark
Mentions using a set or hash map during array traversal.
question_mark
Checks if you can optimize nested loops with incremental counting.

warning

常见陷阱

外企场景

error
Double-counting elements when expanding subarrays without proper hash tracking.
error
Forgetting to square the distinct counts before summing.
error
Assuming all elements are unique without handling duplicates.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sum of cubes of distinct element counts instead of squares.
arrow_right_alt
Compute distinct counts only for subarrays of fixed length.
arrow_right_alt
Count distinct element contributions modulo a large prime for large arrays.

help

常见问题

外企场景

继续练习

#2910 合法分组的最少组数 #2902 和带限制的子多重集合的数目 #2897 对数组执行操作使平方和最大