LeetCode代码优化求助：求二进制数组等01最长连续子数组

你的两个版本代码都存在时间复杂度过高的问题（O(n²)），处理大数组时必然超时。核心问题是重复计算子数组的0/1数量，完全没必要每次都重新统计整个子数组。下面是彻底的优化思路和实现：

问题转化：前缀和+哈希表 #

把数组中的0替换为-1，那么"0和1数量相等的子数组"等价于"子数组元素和为0"。我们可以用前缀和快速判断：

• 前缀和：从数组开头到当前位置的元素累加和
• 如果两个位置的前缀和相等，说明这两个位置之间的子数组和为0，也就是0和1数量相等

用哈希表存储每个前缀和第一次出现的索引，后续遇到相同前缀和时，就能直接计算出最长的符合条件的子数组长度。

优化后的代码 #

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        prefix_sum = 0
        sum_index_map = {0: -1}  # 初始前缀和0对应索引-1，处理从开头就符合条件的情况
        max_len = 0
        
        for idx, num in enumerate(nums):
            # 0转成-1，1保持1，更新前缀和
            prefix_sum += 1 if num == 1 else -1
            
            # 如果当前前缀和已经出现过，计算子数组长度
            if prefix_sum in sum_index_map:
                current_len = idx - sum_index_map[prefix_sum]
                if current_len > max_len:
                    max_len = current_len
            else:
                # 只存第一次出现的索引，保证子数组最长
                sum_index_map[prefix_sum] = idx
        
        return max_len

旧代码超时原因分析 #

• Version2：每次把子数组转成字符串再统计0/1，字符串拼接和count操作都是O(k)（k为子数组长度），整体时间复杂度O(n²)，且字符串操作额外消耗内存。
• Version3：每次用sum(filter)计算子数组的1的数量，同样是O(k)的重复计算，整体还是O(n²)，对于长度10^5的数组，这样的复杂度完全无法通过时间限制。

优化后的优势 #

• 时间复杂度：O(n)，仅遍历数组一次，哈希表的查询和插入均为O(1)
• 空间复杂度：O(n)，最坏情况下所有前缀和都不同，哈希表存储n+1个键值对，完全符合LeetCode内存限制

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