2916. Subarrays Distinct Element Sum of Squares II
Description
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 ofnums
consisting of all the indices fromi
toj
such that0 <= i <= j < nums.length
. Then the number of distinct values innums[i..j]
is called the distinct count ofnums[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
Solutions
Solution 1
1 |
|
1 |
|
1 |
|
1 |
|