我需要帮助了解此解决方案中如何考虑所有子数组

Question

问题：

给定一个 0 索引的整数数组 nums。 nums 子数组的不同计数定义为： 令

nums[i..j]

为 nums 的子数组，由从 i 到 j 的所有索引组成，使得

0 <= i <= j < nums.length

。那么

nums[i..j]

中不同值的数量称为

nums[i..j]

的不同值计数。

返回 nums 的所有子数组的不同计数的平方和。

子数组是数组中连续的非空元素序列。

这是网上的解决方案，因为我自己无法解决它，但我不明白它如何考虑所有子数组：

解决方案：

    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]

它认为：

[1,2,1]

然后：

[2,1]

然后

[1]

但是

[2]

和

[1]

呢？

我很困惑我哪里出错了。请帮助我理解它。

Answer 1

内循环的每次迭代对应一个子数组。

第一次迭代外循环：

i == 0

第一次迭代内循环：

j == 0

，子数组为

{1}

，该子数组的目标值通过

(hash.size() * hash.size())

计算并累积在

result

中。

第二次迭代内循环：

j == 1

，子数组为

{1,2}

，使用相同的hashmap，只添加最后一个元素。目标值的计算与之前相同并累积在

target

中。

...等等...

您缺少的子数组是：

{2}

，即外循环的第二次迭代，内循环的第一次迭代，即当

i == 1

（子数组的起始索引）和

j == 1

（子数组的结束索引）时。

{1}

，外循环第三次迭代，内循环第一次迭代。

您应该使用调试器来查看这一点。