求助：Hackerrank选数问题C#代码超时优化

我正在解决Hackerrank的「选数（Picking Numbers）」问题，要求从给定整数数组中选取最长子数组，满足子数组内任意两元素的绝对差值≤1。现有代码能正确运行，但超出时间限制，代码如下：

public static int pickingNumbers(List<int> a)
{
    List<List<int>> arrList = new List<List<int>>();
    List<List<int>> arrSkipList = new List<List<int>>();

    int i = 0;

Start:
    int elementToCompare = a[i];

    List<int> arr = new List<int>();
    arr.Add(elementToCompare);

    for (int j = i + 1; j < a.Count; j++)
    {
        if (Math.Abs(elementToCompare - a[j]) <= 1)
        {
            var tempList = new List<int>(arr);
            tempList.Add(a[j]);

            //check if the sequence matches any existing one to skip
            if (arrList.Any(x => string.Join("", x).StartsWith(string.Join("", tempList))))
            {
                continue;
            }

            //check if sequence is present in skiplist added before(below this for loop)
            if (arrSkipList.Any(x => string.Join("", x).StartsWith(string.Join("", tempList))))
            {
                continue;
            }

            arr.Add(a[j]);
            elementToCompare = a[j];
        }
    }

    if (arr.Count > 1)
    {
        //For avoiding sequence with length <= the len of existing sequences and add to skiplist
        if (arrList.Count == 0)
        {
            arrList.Add(arr);
        }
        else
        {
            if (arrList.Any(x => arr.Count > x.Count))
                arrList.Add(arr);
            else
                arrSkipList.Add(arr);
        }

        arrList.Add(arr);
        goto Start;
    }

    //check end of list
    if (i < a.Count - 1)
    {
        i++;
        goto Start;
    }

    //counting the max sub-arr
    int max = -1;
    foreach (var pair in arrList)
    {
        Console.Write("[");
        int x = 0;
        foreach (int number in pair)
        {
            Console.Write($"{number}");
            if (x == pair.Count - 1)
            {

            }
            else
            {
                Console.Write(" ");
            }
            x++;
        }
        Console.Write("]");
        Console.WriteLine();


        if (pair.Count > max)
        {
            max = pair.Count;
        }
    }

    return max;
}

原代码性能瓶颈分析 #

• 用goto跳转导致逻辑混乱，可读性差，且容易触发重复计算
• 通过string.Join拼接字符串判断子序列，字符串操作本身耗时，搭配Any遍历列表的操作让这部分时间复杂度急剧上升
• 维护多个子数组列表，占用额外空间的同时，重复判断逻辑冗余
• 嵌套循环遍历数组，时间复杂度接近O(n²)，大规模输入下必然超时

高效解法实现 #

核心思路：合法子数组只能由单一数字或两个相邻数字（如k和k+1）组成。统计每个数字的出现频率后，计算相邻数字的频率之和，最大值就是答案。

public static int pickingNumbers(List<int> a)
{
    // 题目中数字范围为0-100，用固定大小的数组统计频率
    int[] frequency = new int[101];
    foreach (int num in a)
    {
        frequency[num]++;
    }

    int maxLength = 0;
    // 遍历所有相邻数字对，计算总出现次数
    for (int i = 0; i < 100; i++)
    {
        int currentTotal = frequency[i] + frequency[i + 1];
        if (currentTotal > maxLength)
        {
            maxLength = currentTotal;
        }
    }

    return maxLength;
}

高效解法优势 #

• 时间复杂度O(n)：仅需两次线性遍历（一次统计频率，一次计算最大值）
• 空间复杂度O(1)：频率数组大小固定为101，属于常数空间
• 逻辑简洁，完全避免了复杂的子数组判断和字符串操作，性能远超原代码

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