-----------------第二天------------------------
面试官 : 好的， 我们再来做个算法题吧。平时工作中会尝试用算法吗， 用到了什么数据结构？
3妹 : 有用到， 用到了 bla bla…
面试官 : 好的， 题目是这样的：
1题目：
给你一个下标从 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
2思路：
1、使用哈希表统计各数字出现次数。
2、枚举每个元素，分别作为子数组的起始元素，每次步长递增1，使用列表记录步长的统计结果。
3、引用的方式，错位继承步长+1的结果。以{1,2,3}为例，起始元素为2且步长为1的结果，等于上一个起始元素1且步长为3的结果，并去掉元素1。
3java代码：
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;
}
}