Medium

题目描述

给定一个整数数组 nums。

如果 nums 的一个子数组的元素和等于该子数组中的至少一个元素，则称该子数组为居中子数组。

返回 nums 中居中子数组的数量。

示例 1：

输入：nums = [-1,1,0]
输出：5
解释：
- 所有单元素子数组（[-1], [1], [0]）都是居中的。
- 子数组 [1, 0] 的和为 1，而 1 存在于该子数组中。
- 子数组 [-1, 1, 0] 的和为 0，而 0 存在于该子数组中。
因此，答案是 5。

示例 2：

输入：nums = [2,-3]
输出：2
解释：
只有单元素子数组（[2], [-3]）是居中的。

约束条件：

  • 1 <= nums.length <= 500
  • -10^5 <= nums[i] <= 10^5

解题思路

解题思路

这道题要求我们找出所有"居中"的子数组，即子数组的元素和等于其中至少一个元素的子数组。

核心思路：

  1. 暴力枚举：由于数组长度最多500，我们可以枚举所有可能的子数组
  2. 哈希表优化：对于每个子数组，使用哈希表记录其中的元素，然后检查子数组和是否存在于哈希表中

算法步骤：

  1. 遍历所有可能的起始位置 i
  2. 对于每个起始位置，扩展子数组的结束位置 j
  3. 维护当前子数组的元素和 sum 和元素集合 elementSet
  4. 检查 sum 是否在 elementSet 中，如果是则计数器加1

时间复杂度分析：

  • 外层循环：O(n)
  • 内层循环：O(n)
  • 哈希表查找：O(1)
  • 总体：O(n²)

由于约束条件较小（n ≤ 500），这种解法完全可行。所有单元素子数组都是居中的，因为元素和就等于该元素本身。

代码实现

class Solution {
public:
    int centeredSubarrays(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            unordered_set<int> elementSet;
            int sum = 0;
            
            for (int j = i; j < n; j++) {
                elementSet.insert(nums[j]);
                sum += nums[j];
                
                if (elementSet.count(sum)) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def centeredSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        
        for i in range(n):
            element_set = set()
            sum_val = 0
            
            for j in range(i, n):
                element_set.add(nums[j])
                sum_val += nums[j]
                
                if sum_val in element_set:
                    count += 1
        
        return count

public class Solution {
    public int CenteredSubarrays(int[] nums) {
        int n = nums.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            HashSet<int> elementSet = new HashSet<int>();
            int sum = 0;
            
            for (int j = i; j < n; j++) {
                elementSet.Add(nums[j]);
                sum += nums[j];
                
                if (elementSet.Contains(sum)) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var centeredSubarrays = function(nums) {
    const n = nums.length;
    let count = 0;
    
    for (let i = 0; i < n; i++) {
        const elementSet = new Set();
        let sum = 0;
        
        for (let j = i; j < n; j++) {
            elementSet.add(nums[j]);
            sum += nums[j];
            
            if (elementSet.has(sum)) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)双重循环遍历所有子数组，哈希表操作为O(1)
空间复杂度O(n)哈希表存储子数组中的元素，最多n个元素