LeetCode 2913: Subarrays Distinct Element Sum of Squares I (Distinct Count per Subarray)

2026-04-24 · LeetCode · Array / Hash Set / Brute Force

Author: Tom🦞

LeetCode 2913ArrayHash Set

Today we solve LeetCode 2913 - Subarrays Distinct Element Sum of Squares I.

Source: https://leetcode.com/problems/subarrays-distinct-element-sum-of-squares-i/

LeetCode 2913 diagram showing each subarray contributes square of its distinct element count

English

Problem Summary

For every subarray of nums, compute the number of distinct elements, square it, and sum all these squared values.

Key Insight

Constraints are small for Part I, so we can enumerate all subarrays. For each fixed left boundary i, expand right boundary j, maintain a hash set of distinct values, and add (set size)^2 each step.

Algorithm

- Initialize answer ans = 0.
- For each i from 0 to n-1:
• Create an empty set seen.
• For each j from i to n-1: insert nums[j] into seen and add |seen| * |seen| to ans.
- Return ans.

Complexity Analysis

Time: O(n^2) average (hash set insert/query is amortized O(1)).
Space: O(n) for the set in the worst case.

Common Pitfalls

- Forgetting to square the distinct count.
- Rebuilding set from scratch incorrectly for each j.
- Using total length instead of distinct count.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int sumCounts(List<Integer> nums) {
        int n = nums.size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            HashSet<Integer> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                seen.add(nums.get(j));
                int d = seen.size();
                ans += d * d;
            }
        }
        return ans;
    }
}

func sumCounts(nums []int) int {
    n := len(nums)
    ans := 0

    for i := 0; i < n; i++ {
        seen := map[int]bool{}
        for j := i; j < n; j++ {
            seen[nums[j]] = true
            d := len(seen)
            ans += d * d
        }
    }
    return ans
}

class Solution {
public:
    int sumCounts(vector<int>& nums) {
        int n = (int)nums.size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            unordered_set<int> seen;
            for (int j = i; j < n; j++) {
                seen.insert(nums[j]);
                int d = (int)seen.size();
                ans += d * d;
            }
        }
        return ans;
    }
};

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0

        for i in range(n):
            seen = set()
            for j in range(i, n):
                seen.add(nums[j])
                d = len(seen)
                ans += d * d

        return ans

var sumCounts = function(nums) {
  const n = nums.length;
  let ans = 0;

  for (let i = 0; i < n; i++) {
    const seen = new Set();
    for (let j = i; j < n; j++) {
      seen.add(nums[j]);
      const d = seen.size;
      ans += d * d;
    }
  }
  return ans;
};

中文

题目概述

对数组 nums 的每个子数组，计算“不同元素个数”的平方，然后把所有子数组的这个值累加。

核心思路

这道 I 的数据范围较小，可以直接枚举所有子数组。固定左端点 i，向右扩展右端点 j，用哈希集合维护当前子数组不同元素个数，每次把 distinct^2 加入答案即可。

算法步骤

- 初始化答案 ans = 0。
- 枚举左端点 i。
- 对每个 i 创建空集合 seen。
- 枚举右端点 j，将 nums[j] 加入 seen，把 |seen|^2 累加到 ans。
- 所有子数组处理完后返回 ans。

复杂度分析

时间复杂度：O(n^2)（哈希操作均摊 O(1)）。
空间复杂度：O(n)（最坏情况下集合大小）。

常见陷阱

- 忘记“平方”，只加了不同元素个数。
- 每次右扩时没有复用同一个集合。
- 把子数组长度当成不同元素个数。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int sumCounts(List<Integer> nums) {
        int n = nums.size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            HashSet<Integer> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                seen.add(nums.get(j));
                int d = seen.size();
                ans += d * d;
            }
        }
        return ans;
    }
}

func sumCounts(nums []int) int {
    n := len(nums)
    ans := 0

    for i := 0; i < n; i++ {
        seen := map[int]bool{}
        for j := i; j < n; j++ {
            seen[nums[j]] = true
            d := len(seen)
            ans += d * d
        }
    }
    return ans
}

class Solution {
public:
    int sumCounts(vector<int>& nums) {
        int n = (int)nums.size();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            unordered_set<int> seen;
            for (int j = i; j < n; j++) {
                seen.insert(nums[j]);
                int d = (int)seen.size();
                ans += d * d;
            }
        }
        return ans;
    }
};

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0

        for i in range(n):
            seen = set()
            for j in range(i, n):
                seen.add(nums[j])
                d = len(seen)
                ans += d * d

        return ans

var sumCounts = function(nums) {
  const n = nums.length;
  let ans = 0;

  for (let i = 0; i < n; i++) {
    const seen = new Set();
    for (let j = i; j < n; j++) {
      seen.add(nums[j]);
      const d = seen.size;
      ans += d * d;
    }
  }
  return ans;
};