GESP 四级 · GESP 202509 C++ 四级 第 14 题

假设有一个班级的成绩单，存储在一个长度为 $n$ 的数组 scores 中，每个元素是一个学生的分数。老师想要找出所有满足 scores[i] + scores[j] + scores[k] == 300 的三元组，其中 $i < j < k$。下面代码实现该功能，请问其时间复杂度是（ ）。

int cnt = 0;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            if (scores[i] + scores[j] + scores[k] == 300) {
                cnt++;
            }
        }
    }
}

答案C。在循环中遍历数组并累积结果时，注意累加变量的初始值和每次循环的更新方式。

for循环体可能一次都不执行！这是和while循环一样的"先判断后执行"机制。

【考点】时间复杂度｜循环嵌套｜空间复杂度

1. 🎯 考纲定位（考点定位）

本题考查《GESP 四级算法》模块的时间复杂度分析。四级大纲明确要求"能分析简单嵌套循环的时间复杂度"，这道题卡住的是那些只背结论、不懂推导过程的考生——他们看到三层循环就慌，要么凭直觉选 O(n²)，要么把循环次数简单相加。命题人就是要用这道题检验你是否真正理解大 O 表示法的本质：不管循环体内做什么，只要循环结构不变，复杂度就不变。