编码挑战超时问题求解：管道与星号计数算法优化

AI 小北

2026-8-20

编码练习优化问题：统计指定区间内成对管道间的星号数量

题目要求

输入为包含|和*的字符串（例如**|*|*|**|***），实现函数List<int> countItems(string line, List<int> startLocations, List<int> endLocations)，统计位于成对|之间的*字符数量。其中startLocations和endLocations是字符串line中需考虑的起始和结束位置数组（1-based索引）。

示例：

若line=*|*|*，startLocations=[1]，endLocations=[3]，需检查子串*|*，因仅有1个管道，结果为0；
若范围是1到5，结果为1，因仅有1个*在两个管道之间。

遇到的问题

我写出的代码能通过约半数测试用例，但其余因超时（超过3秒）失败。推测需要仅遍历字符串一次的优化方案，想了解此类问题的解决思路、相关概念及同类编程练习资源。

我的代码

List<int> countItems(string line, List<int> startLocations, List<int> endLocations)
{
    var results = new List<int>();
    
    if (String.IsNullOrWhiteSpace(line) || startLocations.Count == 0)
    {
        return results;
    }

    for (var i = 0; i < startLocations.Count; i++)
    {
        var startIndex = startLocations[i] - 1;
        var endIndex = endLocations[i] - 1;

        var start = false;
        var total = 0;
        var tempTotal = 0;

        for (var j = startIndex; j < endIndex; j++)
        {
            if (!start && line[j] == '|')
            {
                start = true;
                tempTotal = 0;
            }
            else if (start && line[j] == '*')
            {
                tempTotal++;
            }
            else if (line[j] == '|')
            {
                total += tempTotal;
                tempTotal = 0;
            }
        }

        if (line[endIndex] == '|')
        {
            total += tempTotal;
        }

        results.Add(total);
    }

    return results;
}

优化思路与解决方案

核心问题分析

原代码的时间复杂度为O(Q*N)（Q为查询次数，N为字符串长度），当Q和N都较大时（如均为10^{5级别），总操作量会达到10}10，必然触发超时。需要将时间复杂度优化到O(N + Q*logN)，核心思路是预处理静态数据+二分查找快速查询。

预处理关键数据

只需要遍历字符串一次，生成三个核心数组：

pipePositions：存储所有|在字符串中的0-based索引，后续用于快速定位查询区间内的管道。
totalStars：前缀和数组，totalStars[i]表示字符串前i个字符（0到i-1）中*的总数，用于快速计算任意区间内的*数量。
pairPrefix：前缀和数组，pairPrefix[k]表示前k对相邻管道之间的*总数（即pipePositions[0]-pipePositions[1]到pipePositions[k-1]-pipePositions[k]的*总和）。

优化后的代码实现

List<int> countItems(string line, List<int> startLocations, List<int> endLocations)
{
    var results = new List<int>();
    if (string.IsNullOrWhiteSpace(line) || startLocations.Count == 0)
        return results;

    // 预处理1：收集所有管道的位置
    List<int> pipePositions = new List<int>();
    for (int i = 0; i < line.Length; i++)
    {
        if (line[i] == '|')
            pipePositions.Add(i);
    }

    // 预处理2：*的前缀和数组
    List<int> totalStars = new List<int>(line.Length + 1);
    totalStars.Add(0);
    int starCount = 0;
    for (int i = 0; i < line.Length; i++)
    {
        if (line[i] == '*')
            starCount++;
        totalStars.Add(starCount);
    }

    // 预处理3：成对管道间*的前缀和数组
    List<int> pairPrefix = new List<int>();
    pairPrefix.Add(0);
    for (int k = 0; k < pipePositions.Count - 1; k++)
    {
        int leftPipe = pipePositions[k];
        int rightPipe = pipePositions[k + 1];
        // 计算当前管道对之间的*数量
        int starsBetween = totalStars[rightPipe] - totalStars[leftPipe + 1];
        pairPrefix.Add(pairPrefix.Last() + starsBetween);
    }

    // 处理每个查询
    for (int i = 0; i < startLocations.Count; i++)
    {
        int start = startLocations[i] - 1;
        int end = endLocations[i] - 1;

        // 找到第一个 >= start 的管道索引
        int leftPipeIdx = pipePositions.BinarySearch(start);
        if (leftPipeIdx < 0)
            leftPipeIdx = ~leftPipeIdx;

        // 找到最后一个 <= end 的管道索引
        int rightPipeIdx = pipePositions.BinarySearch(end);
        if (rightPipeIdx < 0)
            rightPipeIdx = ~rightPipeIdx - 1;

        // 没有成对管道的情况
        if (rightPipeIdx <= leftPipeIdx)
        {
            results.Add(0);
            continue;
        }

        // 计算有效成对管道间的*总数
        results.Add(pairPrefix[rightPipeIdx] - pairPrefix[leftPipeIdx]);
    }

    return results;
}

编码挑战超时问题求解：管道与星号计数算法优化

题目要求 #

遇到的问题 #

我的代码 #

优化思路与解决方案 #

核心问题分析 #

预处理关键数据 #

优化后的代码实现 #

相关概念 #

同类编程练习资源 #