如何消除嵌套for循环将时间复杂度优化至O(n)？

问题背景 #

原代码的getResponse()方法采用嵌套for循环，时间复杂度达O(n²)，无法适配大规模序列数据。该代码核心功能为：

• 接收用户输入的10位整数序列字符串（如"0123456789"）
• 接收大小写敏感的大写PIN码（如"HAM"）
• 将PIN码字符转换为手机键盘对应数字（如ABC→2、DEF→3等）
• 以转换后的数字作为序列数组索引，生成响应字符串（例：输入序列"0123456789"、PIN码"HAM"，响应为"426"）

需求是优化getResponse()的循环逻辑，避免时间复杂度随n²增长，能否直接将letterToPhone返回的数字值与[0-9]整数范围匹配实现？

优化方案：完全可行，彻底消除O(n²)复杂度 #

当然可以，这是最直接的优化路径，能将时间复杂度降至O(k)（k为PIN码的长度），完全适配大规模序列数据。

核心优化思路 #

原嵌套循环的冗余点在于：拿到letterToPhone返回的数字后，还遍历整个序列查找对应位置——这完全没必要。因为letterToPhone返回的数字本身就是0-9范围内的整数，而序列是固定长度为10的字符串，其合法索引正好是0到9，转换后的数字直接就是序列的索引值。

具体实现步骤 #

1. 遍历PIN码的每个字符，调用letterToPhone得到对应的数字x（0-9）
2. 直接通过sequence.charAt(x)（或序列数组的[x]）获取响应字符
3. 将所有响应字符拼接成最终结果
4. 可选：添加x的合法性判断（确保x在0-9范围内），处理非法输入

代码对比 #

原O(n²)代码

public String getResponse(String sequence, String pin) {
    StringBuilder response = new StringBuilder();
    char[] seqArr = sequence.toCharArray();
    for (char c : pin.toCharArray()) {
        int x = letterToPhone(c);
        // 嵌套循环：遍历序列查找数字位置，冗余操作
        for (int i = 0; i < seqArr.length; i++) {
            if (Character.getNumericValue(seqArr[i]) == x) {
                response.append(seqArr[i]);
                break;
            }
        }
    }
    return response.toString();
}

优化后O(k)代码

public String getResponse(String sequence, String pin) {
    StringBuilder response = new StringBuilder();
    for (char c : pin.toCharArray()) {
        int x = letterToPhone(c);
        // 直接用x作为索引取序列对应字符，无嵌套循环
        if (x >= 0 && x <= 9) {
            response.append(sequence.charAt(x));
        }
        // 可添加非法字符的 fallback 逻辑
    }
    return response.toString();
}

关键说明 #

• 优化后无论序列数据规模多大（只要长度固定为10），方法的时间复杂度只和PIN码长度相关，完全不会随序列规模增长而上升。
• 添加x >=0 && x <=9的判断是为了兼容letterToPhone可能返回的非法值（比如输入非大写字母字符），提升代码健壮性。

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