2913.子数组不同元素数目的平方和 I：第一题先常数很大的O(n^2)

【LetMeFly】2913.子数组不同元素数目的平方和 I：第一题先常数很大的O(n^2)

力扣题目链接：https://leetcode.cn/problems/subarrays-distinct-element-sum-of-squares-i/

给你一个下标从 0 开始的整数数组 nums 。

定义 nums 一个子数组的 不同计数 值如下：

• 令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。

请你返回 nums 中所有子数组的 不同计数 的 平方 和。

由于答案可能会很大，请你将它对 109 + 7 取余 后返回。

子数组指的是一个数组里面一段连续 非空 的元素序列。

 

示例 1：

输入：nums = [1,2,1]
输出：15
解释：六个子数组分别为：
[1]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[1]: 1 个互不相同的元素。
[1,2]: 2 个互不相同的元素。
[2,1]: 2 个互不相同的元素。
[1,2,1]: 2 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 + 22 + 22 + 22 = 15 。

示例 2：

输入：nums = [2,2]
输出：3
解释：三个子数组分别为：
[2]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[2,2]: 1 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 = 3 。

 

提示：

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

解题方法：二重循环模拟

第一重循环用变量$i$枚举子数组起点，第二重循环用变量$j$枚举子数组终点，使用一个set来统计子数组中不同元素的个数，并将哈希表大小的平方累加到答案中。在第二重循环的过程中直接将$j$对应的元素加入到哈希表中。

• 时间复杂度$O(len(nums)^2)$
• 空间复杂度$O(len(nums))$

AC代码

C++

/*
 * @LastEditTime: 2026-10-15 22:22:31
 */
class Solution {
public:
    int sumCounts(vector<int>& nums) {
        int ans = 0;
        for (int i = 0, n = nums.size(); i < n; i++) {
            unordered_set<int> se;
            for (int j = i; j < n; j++) {
                se.insert(nums[j]);
                ans += se.size() * se.size();
            }
        }
        return ans;
    }
};

End

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源