调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

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

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

  • 令 nums[i..j] 表示 nums 中所有下标在 ij 范围内的元素构成的子数组(满足 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 <= 105
  • 1 <= nums[i] <= 105
通过次数
2.2K
提交次数
5.6K
通过率
39.1%


相关企业

提示 1
Consider the sum of the count of distinct values of subarrays ending with index i, let’s call it sum. Now if you need the sum of all subarrays ending with index i + 1 think how it can be related to sum and what extra will be needed to add to this.

提示 2
You can find that extra sum using the segment tree.

评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
nums =
[1,2,1]
Source