Easy

题目描述

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

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

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

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

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

示例 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 = [1,1]
输出：3
解释：三个可能的子数组是：
[1]: 1 个不同值
[1]: 1 个不同值
[1,1]: 1 个不同值
所有子数组不同计数的平方和等于 1² + 1² + 1² = 3 。

提示：

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

解题思路

解题思路

这道题要求计算所有子数组中不同元素个数的平方和。由于数组长度最大为100，我们可以使用暴力枚举的方法。

核心思路：

  1. 枚举所有可能的子数组 [i, j]（其中 0 <= i <= j < n）
  2. 对于每个子数组，使用哈希集合（Set）来统计不同元素的个数
  3. 将每个子数组的不同元素个数进行平方，然后累加到结果中

算法步骤：

  1. 使用两层循环枚举所有子数组的起始位置 i 和结束位置 j
  2. 对于每个子数组 nums[i...j]，创建一个新的集合来记录不同元素
  3. 遍历子数组中的每个元素，将其添加到集合中
  4. 集合的大小就是该子数组中不同元素的个数
  5. 将这个个数的平方累加到最终结果中

由于约束条件较小（数组长度 ≤ 100），时间复杂度 O(n³) 是可以接受的。这是一个直观且易于实现的暴力解法。

代码实现

class Solution {
public:
    int sumCounts(vector<int>& nums) {
        int n = nums.size();
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            unordered_set<int> distinct;
            for (int j = i; j < n; j++) {
                distinct.insert(nums[j]);
                int count = distinct.size();
                result += count * count;
            }
        }
        
        return result;
    }
};

class Solution:
    def sumCounts(self, nums: List[int]) -> int:
        n = len(nums)
        result = 0
        
        for i in range(n):
            distinct = set()
            for j in range(i, n):
                distinct.add(nums[j])
                count = len(distinct)
                result += count * count
        
        return result

public class Solution {
    public int SumCounts(IList<int> nums) {
        int n = nums.Count;
        int result = 0;
        
        for (int i = 0; i < n; i++) {
            HashSet<int> distinct = new HashSet<int>();
            for (int j = i; j < n; j++) {
                distinct.Add(nums[j]);
                int count = distinct.Count;
                result += count * count;
            }
        }
        
        return result;
    }
}

var sumCounts = function(nums) {
    const n = nums.length;
    let result = 0;
    
    for (let i = 0; i < n; i++) {
        const distinct = new Set();
        for (let j = i; j < n; j++) {
            distinct.add(nums[j]);
            const count = distinct.size;
            result += count * count;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n²)
空间复杂度O(n)

说明：

  • 时间复杂度： O(n²)，外层循环 O(n)，内层循环平均 O(n)，集合插入操作 O(1)
  • 空间复杂度： O(n)，最坏情况下集合需要存储所有不同的元素