2916-subarrays-distinct-element-sum-of-squares-ii.adoc

2916. Subarrays Distinct Element Sum of Squares II

{leetcode}/problems/subarrays-distinct-element-sum-of-squares-ii/[LeetCode - 2916. Subarrays Distinct Element Sum of Squares II ^]

You are given a *0-indexed *integer array nums.

The distinct count of a subarray of nums is defined as:

• Let nums[i..j] be a subarray of nums consisting of all the indices from i to j such that 0 ⇐ i ⇐ j < nums.length. Then the number of distinct values in nums[i..j] is called the distinct count of nums[i..j].

Return _the sum of the squares of distinct counts of all subarrays of _`nums`.

Since the answer may be very large, return it modulo 109 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,1]
Output: 15
Explanation: Six possible subarrays are:
[1]: 1 distinct value
[2]: 1 distinct value
[1]: 1 distinct value
[1,2]: 2 distinct values
[2,1]: 2 distinct values
[1,2,1]: 2 distinct values
The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 + 22 + 22 + 22 = 15.

Example 2:

Input: nums = [2,2]
Output: 3
Explanation: Three possible subarrays are:
[2]: 1 distinct value
[2]: 1 distinct value
[2,2]: 1 distinct value
The sum of the squares of the distinct counts in all subarrays is equal to 12 + 12 + 12 = 3.

Constraints:

• 1 ⇐ nums.length ⇐ 105

• 1 ⇐ nums[i] ⇐ 105

思路分析

一刷

link:{sourcedir}/_2916_SubarraysDistinctElementSumOfSquaresIi.java[role=include]

参考资料