字符串与数组元素去重后匹配字符计数的Java代码优化求助

原代码处理大输入时效率拉胯，主要问题出在这几点：

• 没对目标字符串B做去重，每次统计都要遍历整个B，重复检查相同字符
• 用String.contains()查字符，每次都是O(k)的时间开销（k是当前字符串长度），次数多了根本扛不住
• 额外存了数组元素去重后的字符串，既占内存，还多了一遍遍历统计的步骤

优化的关键方向 #

1. 先预处理目标字符串B：把B去重后存到快速查找结构里，优先用布尔数组（因为字符的取值范围有限），这样查字符存不存在就是O(1)的速度
2. 边处理数组元素边统计：遍历数组每个元素时，直接对字符去重同时统计符合条件的数量，不用先存去重后的字符串，省内存也省步骤
3. 用布尔数组替代HashSet：字符这种范围有限的类型，布尔数组比HashSet快，没有哈希计算和碰撞的额外开销

优化后的代码 #

static int[] mathProfessor(String B, String[] a) {
    // 预处理B：去重后存入布尔数组，O(1)查找字符是否存在
    boolean[] bChars = new boolean[256]; // 覆盖所有ASCII字符，要支持Unicode可以调整范围
    B.chars().distinct().forEach(c -> bChars[c] = true);

    int[] result = new int[a.length];
    for (int i = 0; i < a.length; i++) {
        String s = a[i];
        boolean[] seen = new boolean[256]; // 记录当前字符串已经处理过的字符，避免重复统计
        int count = 0;
        for (char c : s.toCharArray()) {
            if (!seen[c]) {
                seen[c] = true;
                if (bChars[c]) {
                    count++;
                }
            }
        }
        result[i] = count;
    }
    return result;
}

优化细节说明 #

• 预处理B只做一次：对B去重和初始化布尔数组只执行一次，后面所有数组元素的统计都复用这个结构，避免重复劳动
• 边遍历边完成去重+统计：用seen数组记录已经处理过的字符，确保每个字符只统计一次，同时直接检查是否在B的字符集中，一步到位
• 性能大幅提升：字符查找从原代码的O(k)变成O(1)，整体时间复杂度从原来的O(mn + pq)（m为数组长度，n为数组元素平均长度，p为数组长度，q为B的长度）优化到O(m*n + q)，内存也因为去掉了存去重字符串的List而减少

如果需要支持Unicode字符（比如中文），可以把布尔数组换成HashSet<Integer>，性能略逊但兼容性更好：

static int[] mathProfessorUnicode(String B, String[] a) {
    Set<Integer> bCharSet = B.chars().distinct().boxed().collect(Collectors.toSet());
    int[] result = new int[a.length];
    for (int i = 0; i < a.length; i++) {
        Set<Integer> seen = new HashSet<>();
        int count = 0;
        for (char c : a[i].toCharArray()) {
            int codePoint = (int) c;
            if (seen.add(codePoint)) { // add返回false说明字符已存在，直接跳过
                if (bCharSet.contains(codePoint)) {
                    count++;
                }
            }
        }
        result[i] = count;
    }
    return result;
}

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