为啥这个会死循环？

将 脚本之家 设为“星标⭐”
第一时间收到文章更新

来源公众号：吴师兄学算法  ID：CXYxiaow

今天有个学员来咨询一道算法题：在排序链表一题中，为什么不写 nextnode = None 就会导致超时？

一般来说，LeetCode 编辑器给出 TLE 的错误提示基本上就是以下几个因素导致的，大家后续刷题过程中出现这个提示可以按照这些因素去排查。

1. 算法效率低下：如果你的算法复杂度过高，如使用了 O(n^2) 或更高复杂度的算法解决问题，而问题的数据规模很大，就可能导致超时。
2. 死循环：代码中存在死循环也是常见原因。这可能是因为循环的退出条件设置不正确或根本就没有设置退出条件。
3. 不必要的重复计算：如果代码中存在大量重复的计算，尤其是在递归或循环中，这会大大增加执行时间。
4. 过度复杂的数据结构：使用不恰当的数据结构可能导致操作的时间复杂度过高，比如在需要频繁查询的场景中使用链表而不是数组或哈希表。
5. 输入/输出处理不当：有时候，处理输入输出的方式不够高效，特别是在处理大量数据时，也可能导致超时。

举一些常见的例子。

1. LeetCode 1 - 两数之和（Two Sum）: 如果使用暴力解法，即两层循环遍历所有可能的数对来检查它们的和是否等于目标值，当输入数组非常大时，这种 O(n^2) 的解法会导致超时。更好的解法是使用哈希表，这样可以将时间复杂度降低到 O(n)。
2. LeetCode 15 - 三数之和（3Sum）: 类似于“两数之和”，如果使用三层循环来枚举所有可能的三个数的组合，时间复杂度为 O(n^3)，对于大数据集会超时。一种有效的解法是先对数组排序，然后使用双指针方法，将时间复杂度降低到 O(n^2)。
3. LeetCode 53 - 最大子序和（Maximum Subarray）: 如果使用三层循环来计算所有可能的子数组和，时间复杂度为 O(n^3)，在大数据集上会超时。更高效的解法是使用动态规划或分治法，将时间复杂度降低到 O(n)。
4. LeetCode 70 - 爬楼梯（Climbing Stairs）: 如果使用简单的递归来解决这个问题，由于大量的重复计算，对于较大的输入值会导致超时。使用动态规划或斐波那契数列的公式可以有效避免重复计算，将时间复杂度降低到 O(n)。
5. LeetCode 11 - 盛最多水的容器（Container With Most Water）: 使用两层循环遍历所有可能的线段组合来寻找最大的容量会导致 O(n^2) 的时间复杂度。而使用双指针方法可以将时间复杂度降低到 O(n)。
6. LeetCode 62 - 不同路径（Unique Paths）: 简单递归的方法会导致大量的重复计算，导致超时。动态规划是解决此问题的更高效方法。
7. LeetCode 75 - 颜色分类（Sort Colors）: 如果使用基本的排序算法（如冒泡排序），可能会因为 O(n^2) 的时间复杂度而超时。使用三指针可以将时间复杂度降至 O(n)。
8. LeetCode 121 - 买卖股票的最佳时机（Best Time to Buy and Sell Stock）: 如果使用两层循环来寻找每一对买入和卖出的最大利润，会导致 O(n^2) 的时间复杂度。使用单次遍历即可将复杂度降低到 O(n)。
9. LeetCode 169 - 多数元素（Majority Element）: 使用两层循环来计算每个元素出现的次数会导致 O(n^2) 的时间复杂度。使用摩尔投票算法或哈希表可以有效降低时间复杂度。
10. LeetCode 200 - 岛屿数量（Number of Islands）: 如果使用暴力方法遍历每个格子并在每个格子上执行深度优先搜索，可能会因为重复搜索而超时。适当使用访问标记可以避免重复搜索。
11. LeetCode 217 - 存在重复元素（Contains Duplicate）: 如果使用两层循环来检查每一对元素，时间复杂度为 O(n^2)，可能会超时。使用哈希集合可以将时间复杂度降低到 O(n)。
12. LeetCode 300 - 最长递增子序列（Longest Increasing Subsequence）: 使用 O(n^2) 的动态规划解法可能在某些情况下超时。使用基于二分查找的方法可以将时间复杂度降低到 O(n log n)。
13. LeetCode 322 - 零钱兑换（Coin Change）: 简单递归可能会导致大量重复计算和超时。使用动态规划可以有效降低时间复杂度。
14. LeetCode 416 - 分割等和子集（Partition Equal Subset Sum）: 使用暴力递归可能会导致超时。动态规划是一种更高效的解决方案。

  推荐阅读：