LeetCode全0子数组计数代码报错求助：堆缓冲区溢出排查修复

题目背景 #

给定整数数组nums，返回其中全0子数组的数量。子数组指数组内连续的非空元素序列。
约束：

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
  示例：
  输入：nums = [1,3,0,0,2,0,0,4]
  输出：6
  解释：4个[0]子数组，2个[0,0]子数组，无更长全0子数组，总和为6。

错误代码 #

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
       vector<int> pos;
       long long count = 0;
       for (auto i = 0; i < nums.size(); ++i) {
           if (nums[i] == 0) {
               pos.push_back(i);
               count++;
           }
       } 

        for (auto i = 0; i < pos.size(); ++i) {
            auto j = i + 1;
            while ((pos[j] - pos[j - 1]) == 1 && j < pos.size()) {
                j++;
                count++;
            }
        }

        return count;
    }
};

运行时错误信息 #

==================================================================
==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000100 at pc 0x000000345df0 bp 0x7ffc88139d90 sp 0x7ffc88139d88
READ of size 4 at 0x602000000100 thread T0
    #2 0x7f3d7e95c0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000100 is located 0 bytes to the right of 16-byte region [0x6020000000f0,0x602000000100)
allocated by thread T0 here:
    #4 0x7f3d7e95c0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8010: fa fa fd fd fa fa fd fa fa fa fd fa fa fa 00 00
=>0x0c047fff8020:[fa]fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==31==ABORTING

问题排查 #

• 数组越界错误：while循环中先访问pos[j]再判断j < pos.size()，当j等于pos.size()时，会访问超出vector范围的内存，触发heap-buffer-overflow。
• 计算逻辑低效：原代码通过记录0的位置再遍历统计，不仅额外占用内存，内层循环还会重复统计连续0的子数组，时间复杂度达O(n²)，无法适配n=1e5的约束。

修复方案 #

优化思路 #

直接遍历数组，维护当前连续0的长度current_zero_len：每遇到一个0，就将长度加1，并把该长度加到总计数中（新增的0会带来current_zero_len个新的全0子数组，即包含当前0的所有长度为1到current_zero_len的子数组）；遇到非0时重置长度为0。

修复后的代码 #

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        long long count = 0;
        long long current_zero_len = 0;
        for (int num : nums) {
            if (num == 0) {
                current_zero_len++;
                count += current_zero_len;
            } else {
                current_zero_len = 0;
            }
        }
        return count;
    }
};

代码说明 #

• 遍历过程中仅用两个变量统计，空间复杂度O(1)，时间复杂度O(n)，完全符合题目约束。
• 避免了数组越界问题，同时高效计算出所有全0子数组的数量。

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