Hackerrank pickingNumbers题Python实现代码错误求助

原代码存在的问题 #

• 缺少itertools库导入语句，运行时会直接抛出名称错误
• 对「子数组」概念理解错误，使用itertools.combinations生成的是元素组合而非连续子数组，同时该实现时间复杂度极高，数组长度稍大就会超时无法通过测试
• 计数判断逻辑错误：你统计的是相邻元素差值符合要求的次数，若长度为n的子数组所有相邻元素都满足条件，符合要求的次数应为n-1，你的判断条件count == len(j)永远无法成立
• 循环范围设置错误：遍历长度的起始值为len(a)-1，直接跳过了整个数组都符合条件的情况
• 找到符合条件的最长长度后没有终止逻辑，break仅能跳出内层循环，外层循环仍会无意义执行

正确实现思路 #

因为要求子数组所有元素的绝对差值不超过1，所以符合要求的子数组最多只能包含两个连续的整数。我们可以先统计每个数字出现的频率，再遍历所有数字，计算当前数字和比它大1的数字的总出现次数，取最大值即可。

def pickingNumbers(a):
    # 题目限定数组元素范围为0~100，直接初始化长度为101的频率数组
    freq = [0] * 101
    for num in a:
        freq[num] += 1
    max_len = 0
    for i in range(100):
        current_total = freq[i] + freq[i+1]
        if current_total > max_len:
            max_len = current_total
    return max_len

如果需要基于排序的滑动窗口实现，也可以用如下写法：

def pickingNumbers(a):
    a.sort()
    left = 0
    max_len = 0
    for right in range(len(a)):
        # 右边界元素和左边界元素差值超过1时，移动左边界缩小窗口
        while a[right] - a[left] > 1:
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len

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