vector含10个元素时makeArrayConsecutive2函数测试用例失败排查求助

问题分析与修复 #

题目背景 #

这是CodeFights平台的一道算法题：Ratiorg收到CodeMaster送的不同尺寸的雕像礼物，每个雕像尺寸为非负整数。他想将雕像按从小到大排列，且每个雕像比前一个恰好大1，可能需要补充雕像，求最少补充数量。示例：statues = [6,2,3,8]时，makeArrayConsecutive2(statues)应返回3。

你的代码问题 #

你提供的C++代码在处理包含10个连续元素的vector（如{1,2,...,10}）时出现异常，核心原因是数组下标越界，触发了未定义行为。

来看你代码里的循环逻辑：

for( int i = 0; i<size; i++ ) {
    int dif = statues[i+1] - statues[i] - 1;
    if( dif >= 1 ) {counter+=dif;}
}

当i遍历到size-1（也就是最后一个元素的下标）时，i+1等于size，而vector的有效下标范围是0到size-1，此时访问statues[i+1]会越界读取不属于这个vector的内存内容，这会导致计算出错误的差值，最终返回不符合预期的结果。

其他测试用例看似正常只是巧合——越界访问的内存值刚好没有干扰最终计算，但这属于未定义行为，随时可能引发崩溃或错误输出。

修复方案 #

只需要调整循环的终止条件，让i最多遍历到倒数第二个元素，确保i+1始终是有效的下标：

#include <iostream>
#include <vector>
#include<algorithm>
using std::vector;
int makeArrayConsecutive2(std::vector <int> statues) {
    vector<int>::size_type size = statues.size();
    // 空数组或单个元素时无需补充，直接返回0
    if (size <= 1) return 0;
    sort( statues.begin(), statues.end() );
    int counter = 0;
    // 修改循环条件，避免越界访问
    for( int i = 0; i < size - 1; i++ ) {
        int dif = statues[i+1] - statues[i] - 1;
        if( dif >= 1 ) {counter+=dif;}
    }
    return counter;
}
int main() {
    vector<int> c = {1,2,3,4,5,6,7,8,9,10};
    std :: cout<<"You need "<<makeArrayConsecutive2(c)<<" statues"<<std::endl;
    return 0;
}

另外新增了边界判断：当vector元素数≤1时直接返回0，既符合题目逻辑（不需要补充雕像），也避免了极端情况下的越界风险。

现在运行{1,2,...,10}这个测试用例，会正确返回0，完全符合预期。

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