Subarrays distinct element sum of squares i

Array Hash Table

80.1% acceptance

Feb 25, 2026

182

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. A subarray is a contiguous non-empty sequence of elements within an array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_counts(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut ans = 0i32;
    for i in 0..n {
      let mut seen = std::collections::HashSet::new();
      for j in i..n {
        seen.insert(nums[j]);
        let d = seen.len() as i32;
        ans += d * d;
      }
    }
    ans
  }
}