【教3妹学编程-算法题】2913. 子数组不同元素数目的平方和 I

-----------------第二天------------------------

面试官 : 好的， 我们再来做个算法题吧。平时工作中会尝试用算法吗， 用到了什么数据结构？
3妹 : 有用到， 用到了 bla bla…
面试官 : 好的， 题目是这样的：

题目：

给你一个下标从 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

思路：

1、使用哈希表统计各数字出现次数。
2、枚举每个元素，分别作为子数组的起始元素，每次步长递增1，使用列表记录步长的统计结果。
3、引用的方式，错位继承步长+1的结果。以{1,2,3}为例，起始元素为2且步长为1的结果，等于上一个起始元素1且步长为3的结果，并去掉元素1。

java代码：

class Solution {public int sumCounts(List<Integer> nums) {int sum = 0;int key = (int) (Math.pow(10, 9) + 7);int len = nums.size();// 按步长统计List<HashMap<Integer, Integer>> stepList = new ArrayList<>(len);// 枚举，各个元素分别作为子数组的起始元素for (int i = 0; i < len; i++) {// 步长递增for (int j = 0; i + j < len; j++) {int num = nums.get(i + j);HashMap<Integer, Integer> numCntMap = new HashMap<>();if (i == 0) {if (j == 0) {numCntMap.put(num, 1);} else {// 继承上一次步长-1的结果numCntMap.putAll(stepList.get(j - 1));if (numCntMap.containsKey(num)) {// 和上个元素重复numCntMap.put(num, numCntMap.get(num) + 1);} else {// 不重复numCntMap.put(num, 1);}}} else {if (j == 0) {sum = (sum + 1) % key;continue;} else {// 错位，继承步长+1的结果，并移除上一个元素// numCntMap.putAll(stepList.get(j + 1));// 优化：将putAll每次都要复制遍历全部，改为直接引用numCntMap = stepList.get(j + 1);int preNum = nums.get(i - 1);int preNumCnt = numCntMap.get(preNum);if (preNumCnt == 1) {numCntMap.remove(preNum);} else {numCntMap.put(preNum, preNumCnt - 1);}}}if (i == 0) {stepList.add(numCntMap);} else {// 更新stepList.set(j, numCntMap);}// 累加平方和sum = (sum + (int) (Math.pow(numCntMap.keySet().size(), 2))) % key;}}return sum;}
}