Leetcode中回文数判断数组实现出现heap-buffer-overflow运行时错误

问题背景 #

实现回文数判断程序，用vector时运行正常，改用整数数组后本地测试没问题，但在LeetCode上触发Runtime error。

代码实现 #

#include<iostream> 

class Solution 
{
    int*arr; 
    size_t size; 
    
    // 将数字的各位存入数组的辅助函数
    void helper(int n,int*digits) 
    {
        static int idx=-1; 
        idx++; 
        if((n/10)==0) 
        {
            digits[idx]=n; 
            return; 
        }
        else 
        {
            digits[idx]=(n%10); // 报错行
            helper(n/10,digits); 
        }
    } 

    public: 

    Solution()
        :arr(NULL),size(0) {} 

    bool isPalindrome(int x) 
    {
        int n=x;
        if(x<0) return false; 
        while(x != 0) 
        {
            size++; 
            x/=10; 
        }
        arr=new int[size]; 
        helper(n,arr); 
        for(size_t i=0;i<size;i++) 
            if(arr[i] != arr[size-1-i]) 
                return false; 
        return true; 
    }

    ~Solution() 
    {
        delete[] arr; 
    }

}; 

int main(int argc,char**argv) 
{
    int n; 
    Solution sol;
    printf("Enter a number: "); 
    scanf("%d",&n); 
    printf("Is the number %d a palindrome? %d\n",n,sol.isPalindrome(n));  
    printf("Press any key to continue...\n"); 
    getchar(); 
    getchar(); 
    return EXIT_SUCCESS; 
}

错误信息 #

==23==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x50200000003c at pc 0x562a5f4a30af bp 0x7ffdc7e88500 sp 0x7ffdc7e884f8
WRITE of size 4 at 0x50200000003c thread T0
    #0 0x562a5f4a30ae in Solution::helper(int, int*) solution.cpp:17:24
    #1 0x562a5f4a2df0 in Solution::isPalindrome(int) solution.cpp:17:9
    #2 0x562a5f4a2819 in __helper__ solution.cpp:17:29
    #3 0x562a5f4a2819 in main solution.cpp:17:41
    #4 0x7fa2bc460d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)
    #5 0x7fa2bc460e3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)
    #6 0x562a5f3d1954 in _start (solution+0xab954)
0x50200000003c is located 0 bytes after 12-byte region [0x502000000030,0x50200000003c)
allocated by thread T0 here:
    #0 0x562a5f4a02fd in operator new[](unsigned long) /root/llvm-project/compiler-rt/lib/asan/asan_new_delete.cpp:98:3
    #1 0x562a5f4a2dc2 in Solution::isPalindrome(int) solution.cpp:17:13
    #2 0x562a5f4a2819 in __helper__ solution.cpp:17:29
    #3 0x562a5f4a2819 in main solution.cpp:17:41
    #4 0x7fa2bc460d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)
SUMMARY: AddressSanitizer: heap-buffer-overflow solution.cpp:17:24 in Solution::helper(int, int*)
Shadow bytes around the buggy address:
  0x501ffffffd80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501ffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x501fffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x502000000000: fa fa fd fd fa fa 00[04]fa fa fa fa fa fa fa fa
  0x502000000080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000180: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000200: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x502000000280: 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
==23==ABORTING

问题分析 #

1. 静态变量idx的残留问题：helper函数中的static int idx=-1是核心问题。静态变量在程序运行期间仅初始化一次，第一次调用isPalindrome后idx的值不会自动重置。当LeetCode用多个测试用例批量调用时，idx会在上一次的基础上继续累加，直接超出新分配数组的下标范围，触发堆缓冲区溢出。
2. size变量未重置：size是类成员变量，多次调用isPalindrome时会持续累加，导致分配的数组长度远大于实际需要的长度；输入0时size保持为0，分配空数组后写入操作直接越界。
3. 输入0的边界情况未处理：输入0时while(x !=0)循环不执行，size为0，后续helper尝试写入数组下标0，直接触发越界错误。

修复方案 #

方案1：移除静态变量，用参数传递下标 #

将idx作为参数传递给helper，每次递归手动递增，彻底避免静态变量的残留问题：

// 修改后的helper函数
void helper(int n, int* digits, int idx) 
{
    if((n/10)==0) 
    {
        digits[idx] = n; 
        return; 
    }
    else 
    {
        digits[idx] = n%10; 
        helper(n/10, digits, idx+1); 
    }
}

// 在isPalindrome中调用时传入初始下标0
arr = new int[size];
helper(n, arr, 0);

方案2：重置静态变量（不推荐） #

如果一定要保留静态变量，每次调用helper前强制重置idx：

arr = new int[size];
// 重置静态变量
static int idx = -1;
idx = -1;
helper(n, arr);

这种方式虽能解决当前问题，但静态变量本身容易引发多线程或多次调用的隐患，不建议使用。

方案3：修复边界情况和变量重置 #

在isPalindrome开头重置size，并处理输入0的情况：

bool isPalindrome(int x) 
{
    int n = x;
    size = 0; // 每次调用重置size
    if(x < 0) return false;
    if(x == 0) return true; // 处理0的边界情况
    while(x != 0) 
    {
        size++; 
        x /= 10;
    }
    // 后续代码不变
}

优化方案：无需数组，直接反转数字对比 #

最简洁高效的方式是直接反转数字的后半部分，与前半部分对比，完全避免内存分配问题：

bool isPalindrome(int x) {
    // 负数或末尾为0且不是0的数直接返回false
    if(x < 0 || (x % 10 == 0 && x != 0)) return false;
    int reversed = 0;
    // 反转后半部分数字
    while(x > reversed) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }
    // 奇数长度时，reversed除以10去掉中间位再对比
    return x == reversed || x == reversed / 10;
}

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