元素和等于长度的最长子数组：前缀和存储逻辑存疑

问题回顾 #

我们需要找到数组中最长的子数组，满足子数组的元素和恰好等于它的长度。比如示例中输入[16, -1, 3, -7, 2, 8, 11, 24]，符合条件的最长子数组是[-1, 3, -7, 2, 8]，和为5，长度也为5。

核心数学推导 #

先明确几个定义：

• prefixSum[k]：数组前k个元素的和（prefixSum[0] = 0，prefixSum[1] = arr[0]，prefixSum[i+1] = arr[0]+arr[1]+...+arr[i]）
• 目标子数组范围[left, right]（0-based）：长度为right - left + 1，元素和为prefixSum[right+1] - prefixSum[left]

根据问题要求，元素和等于长度，列出等式：

prefixSum[right+1] - prefixSum[left] = right - left + 1

将等式整理变形，把含right+1的项移到左边，含left的项移到右边：

prefixSum[right+1] - (right+1) = prefixSum[left] - left

我们把prefixSum[k] - k定义为差值变量diff[k]，等式简化为：

diff[right+1] = diff[left]

这意味着：如果遍历到right时，diff[right+1]的值在之前已经出现过（对应某个left），那么子数组[left, right]就满足元素和等于长度的条件，其长度为(right+1) - left。

对代码疑问的解析 #

你提到的currSum-(i+1)其实就是上面推导的diff[right+1]（currSum等于prefixSum[i+1]，i就是当前的right）。

你当前代码中的Line J存储的是currSum（即prefixSum[i+1]），这是错误的——正确的做法应该存储diff[i+1] = currSum-(i+1)，这样才能通过查找相同的diff值找到符合条件的left，从而计算出正确的子数组长度。你的代码返回结果不符合示例（会得到长度4而非5），就是因为存储的是currSum而非diff值，导致计算的子数组范围错误。

修正后的核心代码 #

int longestSubarray(int n, vector<int> &arr) {
    unordered_map<long long,int> m;
    int maxLen = -1;
    long long currSum=0;
    
    // 初始化：prefixSum[0]-0 = 0-0=0，对应k=0（处理子数组从0开始的情况）
    m[0] = 0;
    
    for(int i=0; i<n; i++){
        currSum += arr[i];
        long long diff = currSum - (i+1);
        
        if(m.find(diff) != m.end()){
            // 找到对应的left，计算子数组长度
            int len = (i+1) - m[diff];
            maxLen = max(maxLen, len);
        } else {
            // 只存储首次出现的diff值，保证子数组最长
            m[diff] = i+1;
        }
    }
    return maxLen == -1 ? -1 : maxLen;
}

关键细节说明 #

为什么要存储首次出现的diff值？因为我们要找最长的子数组，对于同一个diff值，只需要记录它第一次出现的位置（最小的left），这样后续遇到相同diff时，计算出的子数组长度才是最大的。

内容的提问来源于stack exchange，提问作者Dae Hyun