Medium

题目描述

给定一个整数数组 capacity。

如果子数组 capacity[l..r] 满足以下条件，则认为它是稳定的：

  • 长度至少为 3
  • 第一个和最后一个元素都等于它们之间所有元素的和（即，capacity[l] = capacity[r] = capacity[l + 1] + capacity[l + 2] + ... + capacity[r - 1]）

返回一个整数，表示稳定子数组的数量。

示例 1：

输入：capacity = [9,3,3,3,9]
输出：2
解释：
- [9,3,3,3,9] 是稳定的，因为第一个和最后一个元素都是 9，它们之间元素的和是 3 + 3 + 3 = 9
- [3,3,3] 是稳定的，因为第一个和最后一个元素都是 3，它们之间元素的和是 3

示例 2：

输入：capacity = [1,2,3,4,5]
输出：0
解释：
没有长度至少为 3 且首尾元素相等的子数组，所以答案是 0

示例 3：

输入：capacity = [-4,4,0,0,-8,-4]
输出：1
解释：
[-4,4,0,0,-8,-4] 是稳定的，因为第一个和最后一个元素都是 -4，它们之间元素的和是 4 + 0 + 0 + (-8) = -4

约束条件：

  • 3 <= capacity.length <= 10^5
  • -10^9 <= capacity[i] <= 10^9

解题思路

这道题的核心是理解稳定子数组的条件并高效计算。

问题分析： 对于子数组 [l, r]（长度至少为3），稳定条件为：

  1. capacity[l] = capacity[r]
  2. capacity[l] = sum(capacity[l+1] ... capacity[r-1])

关键洞察： 使用前缀和数组 p，其中 p[i] 表示前 i 个元素的和。对于稳定子数组 [l, r]：

  • 中间元素和为：p[r-1] - p[l]
  • 稳定条件转化为：capacity[l] = capacity[r] 且 capacity[l] = p[r-1] - p[l]

算法思路：

  1. 计算前缀和数组
  2. 对于每个位置 r，寻找满足条件的位置 l
  3. 条件转化为：capacity[l] = capacity[r] 且 p[l] = p[r-1] - capacity[r]
  4. 使用哈希表维护每个 (value, prefix_sum) 对的出现次数

优化策略： 遍历数组，对于每个右端点 r，在哈希表中查找满足条件的左端点数量，然后将当前位置的信息加入哈希表。

时间复杂度：O(n)，空间复杂度：O(n)。

代码实现

class Solution {
public:
    long long countStableSubarrays(vector<int>& capacity) {
        int n = capacity.size();
        vector<long long> prefix(n + 1, 0);
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + capacity[i];
        }
        
        long long result = 0;
        map<pair<int, long long>, int> freq;
        
        for (int r = 0; r < n; r++) {
            if (r >= 2) {
                // 查找满足条件的左端点
                long long target_prefix = prefix[r] - capacity[r];
                pair<int, long long> target = {capacity[r], target_prefix};
                if (freq.count(target)) {
                    result += freq[target];
                }
            }
            
            // 将当前位置加入哈希表
            pair<int, long long> current = {capacity[r], prefix[r]};
            freq[current]++;
        }
        
        return result;
    }
};

class Solution:
    def countStableSubarrays(self, capacity: List[int]) -> int:
        n = len(capacity)
        prefix = [0] * (n + 1)
        
        # 计算前缀和
        for i in range(n):
            prefix[i + 1] = prefix[i] + capacity[i]
        
        result = 0
        freq = {}
        
        for r in range(n):
            if r >= 2:
                # 查找满足条件的左端点
                target_prefix = prefix[r] - capacity[r]
                target = (capacity[r], target_prefix)
                if target in freq:
                    result += freq[target]
            
            # 将当前位置加入哈希表
            current = (capacity[r], prefix[r])
            freq[current] = freq.get(current, 0) + 1
        
        return result

public class Solution {
    public long CountStableSubarrays(int[] capacity) {
        int n = capacity.Length;
        long[] prefix = new long[n + 1];
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + capacity[i];
        }
        
        long result = 0;
        Dictionary<(int, long), int> freq = new Dictionary<(int, long), int>();
        
        for (int r = 0; r < n; r++) {
            if (r >= 2) {
                // 查找满足条件的左端点
                long targetPrefix = prefix[r] - capacity[r];
                var target = (capacity[r], targetPrefix);
                if (freq.ContainsKey(target)) {
                    result += freq[target];
                }
            }
            
            // 将当前位置加入哈希表
            var current = (capacity[r], prefix[r]);
            if (freq.ContainsKey(current)) {
                freq[current]++;
            } else {
                freq[current] = 1;
            }
        }
        
        return result;
    }
}

var countStableSubarrays = function(capacity) {
    const n = capacity.length;
    const prefix = new Array(n + 1).fill(0);
    
    // 计算前缀和
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + capacity[i];
    }
    
    let result = 0;
    const freq = new Map();
    
    for (let r = 0; r < n; r++) {
        if (r >= 2) {
            // 查找满足条件的左端点
            const targetPrefix = prefix[r] - capacity[r];
            const target = `${capacity[r]},${targetPrefix}`;
            if (freq.has(target)) {
                result += freq.get(target);
            }
        }
        
        // 将当前位置加入哈希表
        const current = `${capacity[r]},${prefix[r]}`;
        freq.set(current, (freq.get(current) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)遍历数组一次，哈希表操作为O(1)
空间复杂度O(n)前缀和数组和哈希表的空间开销