2913. Subarrays Distinct Element Sum of Squares I

1. Description

For each nonempty contiguous subarray of nums, count how many different values it contains.
Square each count and add the results across all subarrays. Return this total, counting subarrays at different positions separately even when their values match.

2. Example

Example 1

Input: nums = [1,2,1]
Output: 15
Explanation: The three single-element subarrays each contribute 1. The other three subarrays each contain two distinct values, contributing $2^2 = 4$ each. The total is $3 + 12 = 15$.

Example 2

Input: nums = [1,1]
Output: 3
Explanation: Both single-element subarrays and the full array contain one distinct value, so the total is $1 + 1 + 1 = 3$.

3. Constraints

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

4. Solutions

Enumeration with Hash Set

n = nums.size()
Time complexity: O(n^2) on average
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// Fix the left endpoint, then extend the right endpoint while tracking distinct values.
class Solution {
public:
    int sumCounts(const vector<int> &nums) {
        const int n = nums.size();
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            unordered_set<int> seen_nums;
            for (int j = i; j < n; ++j) {
                seen_nums.insert(nums[j]);

                sum += seen_nums.size() * seen_nums.size();
            }
        }

        return sum;
    }
};