C++求解两个有序数组并集出现段错误的问题排查及优化

• 数组下标越界访问：判断数组是否升序时直接访问a[n-2]、a[n-3]和b[m-2]、b[m-3]，当n或m小于3时（比如示例2中m=2），会访问到数组下标为负的非法内存，直接触发段错误。
• 最大值计算逻辑错误：仅通过最后三个元素是否升序判断数组最大值的位置完全不可靠，比如数组[100, 1, 2, 3]最后三个元素升序，但最大值是第一个元素100，你会误判最大值为3，后续申请的计数数组长度不够，访问ptr[100]时再次越界触发段错误。
• 可变长度数组栈溢出：C++标准不支持栈上申请可变长度数组（VLA），仅部分编译器做了扩展支持，而且如果最大值接近1e5，栈上申请10万级别的int数组会直接超过栈内存限制，引发栈溢出导致段错误。

根据约束条件0 ≤ a[i], b[i] < 1e5，直接申请固定大小的计数数组即可，不需要动态判断最大值：

//Function to return the count of number of elements in union of two arrays.
int doUnion(int a[], int n, int b[], int m)  {
    const int MAX_VAL = 1e5;
    int cnt[MAX_VAL] = {0};
    for(int i = 0; i < n; i++) {
        cnt[a[i]] = 1;
    }
    for(int i = 0; i < m; i++) {
        cnt[b[i]] = 1;
    }
    int res = 0;
    for(int i = 0; i < MAX_VAL; i++) {
        res += cnt[i];
    }
    return res;
}

题目明确说明两个数组是有序数组，可以用双指针法实现O(n+m)时间复杂度、O(1)额外空间的最优解法：

int doUnion(int a[], int n, int b[], int m)  {
    int i = 0, j = 0, res = 0;
    int prev = -1; // 因为元素≥0，初始值设为-1即可
    while(i < n && j < m) {
        if(a[i] < b[j]) {
            if(a[i] != prev) {
                res++;
                prev = a[i];
            }
            i++;
        } else if(a[i] > b[j]) {
            if(b[j] != prev) {
                res++;
                prev = b[j];
            }
            j++;
        } else {
            if(a[i] != prev) {
                res++;
                prev = a[i];
            }
            i++;
            j++;
        }
    }
    // 处理a数组剩余元素
    while(i < n) {
        if(a[i] != prev) {
            res++;
            prev = a[i];
        }
        i++;
    }
    // 处理b数组剩余元素
    while(j < m) {
        if(b[j] != prev) {
            res++;
            prev = b[j];
        }
        j++;
    }
    return res;
}

这个解法不需要额外申请大数组，也避免了遍历1e5长度的计数数组，性能更高。

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