极简算法时间优化：数组差值匹配循环性能优化咨询

当前代码是双重嵌套的暴力循环，时间复杂度为O(n²)。数组规模越大，循环执行次数会呈平方级暴涨，这是运行速度过慢的根本原因。另外代码本身还有两处可以直接修正的问题：

• 内层循环条件写的是t < N - 1，直接跳过了数组最后一个位置的判断，会导致本该在N-1位置匹配到阈值的结果被误判为未命中
• 每算一个结果就调用一次printf，大数组场景下IO开销占比极高，会进一步拖慢整体速度

基础优化（不改核心逻辑，直接提速度） #

如果数组规模不大（N<1000），不需要重构核心逻辑，只要减少循环内的冗余开销就能获得明显提升：

• 把外层循环里的基准值H[i]、固定阈值VSQR、循环边界提前读成局部变量，避免每次内层循环判断时重复从内存寻址取值
• 开辟一块临时数组存所有计算结果，全算完之后一次性批量输出，砍掉逐次打印带来的高额IO开销
• 修正内层循环的边界错误，把t < N-1改成t < N，保证数组最后一个位置也会参与判断

优化后的基础版代码：

int res[N];
const int vsqr = VSQR;
const int end = N;
for (int i = 0; i < N; i++) {
    int base = H[i];
    int t;
    for (t = i + 1; t < end; t++) {
        if (H[t] - base > vsqr) break;
    }
    res[i] = t - 1;
}
// 批量输出所有结果
for (int i = 0; i < N; i++) {
    printf("%d ", res[i]);
}

高阶优化（适配大数组场景） #

如果数组规模到了万级以上，直接把核心暴力逻辑替换成单调列表+二分查找的结构，整体时间复杂度降到O(nlogn)，性能比原实现高几个数量级：

• 从数组最后一个元素往前遍历，维护一个严格递增的有序列表，列表项存两个值：元素本身的数值、该数值最早出现的数组位置
• 遍历到位置i时，要找的目标值是H[i] + VSQR，直接在这个有序列表里通过二分查找，找到第一个数值大于等于目标值的项，它存储的位置就是需要的t
• 把当前H[i]插入列表前，先把列表里所有数值<=H[i]的项删掉：因为H[i]的值更小、位置更靠前，对前面的基准元素来说，可用性比被删掉的项更强，留着只会增加二分的计算量
• 如果没找到匹配的项，直接取数组末尾位置N-1作为输出结果

这套结构不需要额外的复杂依赖，普通数组就能实现，哪怕N到百万级也能在毫秒级跑完。

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