关于子数组不同元素计数平方和解法的遍历逻辑疑问

给定一个0索引的整数数组nums，子数组的不同元素计数定义为：设nums[i..j]是nums的子数组，包含从i到j的所有索引（满足0 <= i <= j < nums.length），则nums[i..j]中不同值的数量称为该子数组的不同元素计数。

返回所有子数组的不同元素计数的平方和。子数组是数组内连续的非空元素序列。

解法代码 #

int sumCounts(vector<int>& nums) {
    int n = nums.size();
    int result = 0;
    for (int i = 0; i < n; i++) {
        unordered_map<int, int> hash;
        for (int j = i; j < n; j++) {
            hash[nums[j]]++;
            result += (hash.size() * hash.size());
        }
    }
    return result;
}

遍历逻辑详解 #

你误解了双层循环的覆盖范围，它其实枚举了所有可能的子数组。以数组[1,2,1]为例，逐轮拆解循环过程：

第一轮：i=0（子数组起始索引固定为0）

内层j从0到2依次遍历：

• j=0：对应子数组[1]，哈希表size为1，result += 1²=1
• j=1：对应子数组[1,2]，哈希表size为2，result += 2²=4 → 累计5
• j=2：对应子数组[1,2,1]，哈希表size仍为2，result += 2²=4 → 累计9
  这一轮处理了所有以0为起点的子数组：[1]、[1,2]、[1,2,1]

第二轮：i=1（子数组起始索引固定为1）

内层j从1到2依次遍历：

• j=1：对应子数组[2]，哈希表size为1，result +=1²=1 → 累计10
• j=2：对应子数组[2,1]，哈希表size为2，result +=2²=4 → 累计14
  这一轮处理了所有以1为起点的子数组：[2]、[2,1]

第三轮：i=2（子数组起始索引固定为2）

内层j=2：

• j=2：对应子数组[1]，哈希表size为1，result +=1²=1 → 累计15
  这一轮处理了以2为起点的子数组：[1]

所有子数组都被遍历到了，最终结果15就是所有子数组不同元素计数的平方和：1² + 2² + 2² +1² +2² +1² = 1+4+4+1+4+1=15。

本质上，外层循环固定子数组的起始位置i，内层循环从i开始扩展结束位置j，每一次j的移动都对应一个新的子数组nums[i..j]。遍历完所有i，就覆盖了数组中所有可能的非空连续子数组。

内容的提问来源于stack exchange，提问作者Yashasvi Choudhary