Codility GenomicRangeQuery问题大数组查询超时优化求助

问题根源 #

你的代码超时核心在于时间复杂度超标：

• 预处理阶段将字符串转数值数组是O(N)，但查询阶段每个请求都要遍历区间[P[k], Q[k]]，最坏情况下每个查询遍历整个数组（比如P=0、Q=N-1），总时间复杂度达到O(M*N)。
• 当N=1e5、M=5e4时，总操作量突破5e9，远超时间限制。

优化方案：前缀和数组 #

由于Impact值仅4种（A=1、C=2、G=3、T=4），我们可以为每个字符维护前缀和数组，记录到每个位置为止该字符的累计出现次数。查询区间[L, R]时：

1. 先判断区间内是否存在A：若前缀和数组中A在R+1的计数减去L位置的计数大于0，说明区间有A，最小Impact就是1。
2. 若没有A，再判断C是否存在，存在则最小为2。
3. 以此类推，直到找到存在的最小Impact字符。

这种方法预处理时间O(N)，单查询时间O(1)，总时间复杂度O(N+M)，完全适配题目约束。

优化后的代码 #

class Solution {
    public int[] solution(String S, int[] P, int[] Q) {
        int strLen = S.length();
        int queryCount = P.length;
        int[] result = new int[queryCount];
        
        // 前缀和数组，分别对应A、C、G、T的累计出现次数
        int[] prefixA = new int[strLen + 1];
        int[] prefixC = new int[strLen + 1];
        int[] prefixG = new int[strLen + 1];
        int[] prefixT = new int[strLen + 1];
        
        for (int i = 0; i < strLen; i++) {
            // 继承前一位置的计数
            prefixA[i+1] = prefixA[i];
            prefixC[i+1] = prefixC[i];
            prefixG[i+1] = prefixG[i];
            prefixT[i+1] = prefixT[i];
            
            // 根据当前字符更新对应计数
            char currentChar = S.charAt(i);
            switch(currentChar) {
                case 'A':
                    prefixA[i+1]++;
                    break;
                case 'C':
                    prefixC[i+1]++;
                    break;
                case 'G':
                    prefixG[i+1]++;
                    break;
                case 'T':
                    prefixT[i+1]++;
                    break;
            }
        }
        
        // 处理每个查询请求
        for (int i = 0; i < queryCount; i++) {
            int left = P[i];
            int right = Q[i];
            
            if (prefixA[right+1] - prefixA[left] > 0) {
                result[i] = 1;
            } else if (prefixC[right+1] - prefixC[left] > 0) {
                result[i] = 2;
            } else if (prefixG[right+1] - prefixG[left] > 0) {
                result[i] = 3;
            } else {
                result[i] = 4;
            }
        }
        
        return result;
    }
}

额外细节优化 #

• 替换原代码中S.split("")的字符串分割操作，直接用charAt(i)遍历字符，避免分割带来的额外开销。
• 移除冗余的空值判断（题目已明确S非空、P与Q长度一致），简化逻辑。

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