子数组不同元素数目的平方和 I

标签: 数组哈希表

难度: Easy

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

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

令 nums[i..j] 表示 nums 中所有下标在 i 到 j 范围内的元素构成的子数组（满足 0 <= i <= j < nums.length ），那么我们称子数组 nums[i..j] 中不同值的数目为 nums[i..j] 的不同计数。

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

由于答案可能会很大，请你将它对 10⁹ + 7 取余后返回。

子数组指的是一个数组里面一段连续非空的元素序列。

示例 1：

输入：nums = [1,2,1]
输出：15
解释：六个子数组分别为：
[1]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[1]: 1 个互不相同的元素。
[1,2]: 2 个互不相同的元素。
[2,1]: 2 个互不相同的元素。
[1,2,1]: 2 个互不相同的元素。
所有不同计数的平方和为 1² + 1² + 1² + 2² + 2² + 2² = 15 。

示例 2：

输入：nums = [2,2]
输出：3
解释：三个子数组分别为：
[2]: 1 个互不相同的元素。
[2]: 1 个互不相同的元素。
[2,2]: 1 个互不相同的元素。
所有不同计数的平方和为 1² + 1² + 1² = 3 。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100

Submission

运行时间: 39 ms

内存: 16.1 MB

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        # 方法一：
        # n = len(nums)
        # res = 0
        # for j in range(n):
        #     for i in range(j,-1,-1):
        #         num = len(set(nums[i:j+1]))
        #         res += num * num
        # return res

        # 方法二：
        n = len(nums)
        res = 0
        for i in range(n):
            s = set()
            for j in range(i,n):
                s.add(nums[j])
                res += len(s) ** 2
        return res

Explain

题解采用了双层循环的方式来求解不同子数组的不同元素数目的平方和。外层循环遍历数组的起始位置i，内层循环遍历从i开始的结束位置j。为了计算从i到j的子数组中不同元素的数量，使用了一个集合s来存储遍历过程中遇到的元素。每次将j位置的元素加入集合s之后，计算集合大小的平方，然后累加到结果res中。这种方法避免了重复计算每个子数组内不同元素的数量，通过动态维护集合s来实现。

时间复杂度: O(n^2)

空间复杂度: O(n)

# 定义类Solution

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n = len(nums)  # 获取数组长度
        res = 0  # 初始化结果累加器
        for i in range(n):  # 从每个位置i开始
            s = set()  # 初始化集合，用于存储不同元素
            for j in range(i, n):  # 从i到数组末尾
                s.add(nums[j])  # 将元素加入集合
                res += len(s) ** 2  # 计算集合大小的平方并累加到结果中
        return res  # 返回最终结果

Explore

在这种情况下，使用集合(set)是因为集合内部自动处理元素的唯一性，适合用于跟踪不同元素。集合在添加元素时会自动检查并忽略重复项，这使得它非常适合本题目的需求，即统计子数组中不同元素的数量。而哈希表(dict)虽然也可以用来跟踪元素的存在与否，但其主要用途是存储键值对，对于本题只需要知道元素是否存在，使用哈希表会略显冗余。其他数据结构如列表会涉及到更多的查找和插入操作，效率较低。

是的，每次内层循环重新创建集合s会导致不必要的重复计算，因为每个起始位置i的子数组都是重复计算前面已经处理过的元素。可以通过使用滑动窗口或双指针技术来优化这一过程。具体来说，可以维持一个集合并在外层循环中逐步向右移动结束位置j，同时动态更新集合内容（添加新元素或删除不再属于当前子数组的元素），这样就可以避免对每个起始位置i重复初始化集合，从而减少重复工作和提高效率。

是的，不使用模运算可能导致处理大数时出现整数溢出的问题。在实际编程环境中，尤其是当数组长度较大或数组元素多样时，累加的结果可能会超过标准整数类型的存储范围。通常在涉及大量累加运算的算法中，使用模运算（如 % 10^9 + 7）是一种常见的做法来避免溢出，同时保证结果的正确性。建议在实现时加入模运算来提高代码的健壮性。

是的，这种方式能够准确反映所有可能的不同元素组合情况。通过从i到j的子数组中不断添加元素到集合s，可以确保集合中的元素是该子数组中所有不同的元素。每次向集合添加新元素时，集合的大小（即不同元素的数量）都会相应更新，从而能够在每一步中准确计算出不同元素数量的平方。这种方法确保了对每个子数组不同元素的准确统计。