题目描述
给你一个下标从 0 开始的整数数组 nums
。
定义 nums
一个子数组的 不同计数 值如下:
- 令
nums[i..j]
表示nums
中所有下标在i
到j
范围内的元素构成的子数组(满足0 <= i <= j < nums.length
),那么我们称子数组nums[i..j]
中不同值的数目为nums[i..j]
的不同计数。
请你返回 nums
中所有子数组的 不同计数 的 平方 和。
由于答案可能会很大,请你将它对 10^9 + 7
取余 后返回。
子数组指的是一个数组里面一段连续 非空 的元素序列。
样例
输入: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。
输入:nums = [2,2]
输出:3
解释:三个子数组分别为:
[2]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[2,2]: 1 个互不相同的元素。
所有不同计数的平方和为 12 + 12 + 12 = 3。
限制
1 <= nums.length <= 100
1 <= nums[i] <= 100
算法
(暴力枚举,哈希表) $O(n^2)$
- 枚举子数组起始位置 $i$,然后按序枚举终止位置 $j$,枚举过程中维护当前子数组不同元素的个数,并累加答案。
时间复杂度
- 两重循环,时间复杂度为 $O(n^2)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
class Solution {
public:
int sumCounts(vector<int>& nums) {
const int n = nums.size();
const int mod = 1000000007;
int ans = 0;
for (int i = 0; i < n; i++) {
unordered_set<int> seen;
int c = 0;
for (int j = i; j < n; j++) {
if (seen.find(nums[j]) == seen.end()) {
++c;
seen.insert(nums[j]);
}
ans = (ans + c * c) % mod;
}
}
return ans;
}
};