LeetCode最长连续序列：不使用in改写内层循环的暴力实现

我在解决LeetCode的最长连续序列问题时，用到了官方的暴力解法，但想把内层while循环里的in操作符去掉，改成纯暴力遍历的方式。自己写了个版本，但只能处理两个连续数字的情况，没法支持更长的连续序列。另外我也想搞明白，为什么这个暴力解法的空间复杂度是O(n³)。

官方暴力解法代码 #

class Solution:
    def longestConsecutive(self, nums):
        longest_streak = 0

        for num in nums:
            current_num = num
            current_streak = 1

            # 需要改写这部分，去掉in操作符
            while current_num + 1 in nums:
                current_num += 1
                current_streak += 1

            longest_streak = max(longest_streak, current_streak)

        return longest_streak

我尝试的代码（存在问题） #

while j < n and i != j:
    if nums[j] == currentSequenceNumber + 1:
        currentSequenceLength += 1
        currentSequenceNumber = nums[j]
    j += 1

正确的暴力改写版本 #

要实现不用in的纯暴力遍历，核心是每次需要查找current_num + 1时，都完整遍历整个数组去确认是否存在。同时，一旦找到这个数，需要继续查找下一个连续数，所以内层需要嵌套一个循环来完成这个查找过程：

class Solution:
    def longestConsecutive(self, nums):
        longest_streak = 0
        n = len(nums)

        for num in nums:
            current_num = num
            current_streak = 1
            
            # 改写后的内层逻辑：不用in，纯暴力查找连续数
            while True:
                found = False
                # 遍历整个数组找current_num + 1
                for candidate in nums:
                    if candidate == current_num + 1:
                        current_num += 1
                        current_streak += 1
                        found = True
                        break  # 找到就跳出当前遍历，继续找下一个连续数
                if not found:
                    break  # 找不到下一个连续数，结束循环

            longest_streak = max(longest_streak, current_streak)

        return longest_streak

改写逻辑说明 #

• 每次要找current_num + 1时，就遍历整个nums数组，逐个比对元素
• 一旦找到匹配的元素，就更新current_num和current_streak，然后重新开始遍历数组找下一个连续数
• 当某次遍历数组完全找不到current_num + 1时，就退出内层循环

关于空间复杂度O(n³)的解释 #

这里的空间复杂度说法针对的是递归式暴力实现（你提供的迭代版本空间复杂度是O(1)）：

1. 外层循环遍历每个元素，共n次
2. 每个元素对应的内层，最多需要找n个连续数（比如数组是1,2,3,...,n）
3. 每找一个连续数，都需要遍历整个数组，又是n次操作
4. 如果用递归实现这个查找过程，递归调用栈的深度最大是n（比如找1→2→3→...→n，需要n层递归），结合外层n次循环、每层递归内n次遍历的操作，整体的空间复杂度会达到O(n³)，这里指递归栈占用空间加上遍历过程的临时变量等资源消耗。

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