如何正确分配内存并返回二维数组？区间交集代码报错修复

初始错误：空指针访问 #

用户提供的初始代码：

int min (int a, int b){
    return a < b ? a : b;
}
int max (int a, int b){
    return a > b ? a : b;
}

int** intervalIntersection(
        int** firstList, int firstListSize, int* firstListColSize,
        int** secondList, int secondListSize, int* secondListColSize,
        int* returnSize, int** returnColumnSizes){
    int i = 0, j = 0;
    int a = 0;
    int **res;
    while (i < firstListSize && j < secondListSize) {
        int l = max(firstList[i][0], secondList[j][0]);
        int r = min(firstList[i][1], secondList[j][1]);
 
        if (l <= r){
            res[a][0] = l; // 怀疑此处出错
            res[a][1] = r; // 此处也可能出错
            a++;
        }
 
        if (firstList[i][1] < secondList[j][1])
            i++;
        else
            j++;
    }
    res = malloc(sizeof(int) * (a * 2));
    *returnSize = a;
    **returnColumnSizes = 2;
    return res;
}

触发的错误信息：

runtime error: load of null pointer of type 'int *' 

问题分析 #

1. 空指针提前赋值：res仅声明未初始化，属于空指针，循环中直接通过res[a][0]访问内存必然触发空指针错误。
2. 二维数组内存分配错误：后续malloc(sizeof(int) * (a * 2))的分配逻辑错误，res是int**类型，需先分配a个int*指针空间，再为每个指针分配2个int的存储单元。
3. 返回列数处理错误：**returnColumnSizes = 2操作非法，returnColumnSizes是指向数组的指针，需先为其分配内存，再逐个设置每个结果区间的列数（均为2）。

修复后出现的堆缓冲区溢出错误 #

用户修复后遇到的错误信息：

==32==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000258 at pc 0x564ab16e9fdc bp 0x7fff1adb4900 sp 0x7fff1adb48f0
READ of size 4 at 0x602000000258 thread T0
    #2 0x7f1568a4d0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000258 is located 0 bytes to the right of 8-byte region [0x602000000250,0x602000000258)
allocated by thread T0 here:
    #0 0x7f1569692bc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #3 0x7f1568a4d0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa 00 00 fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8010: fa fa 00 fa fa fa 00 00 fa fa 00 fa fa fa 00 fa
  0x0c047fff8020: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
  0x0c047fff8030: fa fa 00 fa fa fa 00 fa fa fa 00 fa fa fa 00 fa
=>0x0c047fff8040: fa fa 00 fa fa fa 00 fa fa fa 00[fa]fa fa fd fa
  0x0c047fff8050: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8060: fa fa fd fa fa fa fd fa fa fa 00 00 fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8090: 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
==32==ABORTING

问题分析 #

堆溢出通常源于内存分配大小不足，或访问了超出分配范围的内存。比如仅分配了a个int*空间但赋值时越界，或returnColumnSizes未正确分配导致非法内存访问。

正确的修复代码 #

解决思路：

1. 先遍历统计交集数量，再分配对应大小的内存，避免动态扩容复杂度；
2. 正确分配二维数组内存：先分配指针数组，再为每个指针分配存储单元；
3. 规范处理returnColumnSizes：分配对应大小的数组，逐个设置列数。

int min(int a, int b) {
    return a < b ? a : b;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int** intervalIntersection(
        int** firstList, int firstListSize, int* firstListColSize,
        int** secondList, int secondListSize, int* secondListColSize,
        int* returnSize, int** returnColumnSizes) {
    int i = 0, j = 0;
    int count = 0;

    // 第一步：统计交集的数量
    while (i < firstListSize && j < secondListSize) {
        int l = max(firstList[i][0], secondList[j][0]);
        int r = min(firstList[i][1], secondList[j][1]);
        if (l <= r) {
            count++;
        }
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }

    // 第二步：分配结果数组的内存
    *returnSize = count;
    int** res = malloc(count * sizeof(int*));
    *returnColumnSizes = malloc(count * sizeof(int));
    for (int k = 0; k < count; k++) {
        res[k] = malloc(2 * sizeof(int));
        (*returnColumnSizes)[k] = 2;
    }

    // 第三步：重新遍历，填充结果
    i = 0;
    j = 0;
    int idx = 0;
    while (i < firstListSize && j < secondListSize) {
        int l = max(firstList[i][0], secondList[j][0]);
        int r = min(firstList[i][1], secondList[j][1]);
        if (l <= r) {
            res[idx][0] = l;
            res[idx][1] = r;
            idx++;
        }
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }

    return res;
}

代码说明 #

1. 统计交集数量：先遍历一次两个区间列表，计算交集总数，为后续内存分配提供准确大小。
2. 内存分配：
   • 为res分配count个int*空间，每个int*指向一个包含2个int的数组；
   • 为returnColumnSizes分配count个int空间，每个元素设为2，标识每个结果区间的列数。
3. 填充结果：重新遍历列表，将交集的左右端点存入结果数组。

示例验证 #

输入：

firstList = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]

输出：

[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

该代码可正确输出上述结果，无内存错误。

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