1. 算法训练营开营二分查找与数组操作实战第一次参加算法训练营的学员往往会对数组基础操作感到既熟悉又陌生。熟悉是因为数组作为最基本的数据结构几乎出现在所有编程语言中陌生则是因为在实际解题时总会出现各种边界条件问题。今天的三个题目——704二分查找、27移除元素和977有序数组的平方恰好构成了数组操作的铁三角查找、删除和转换。我在刷题初期曾花费整整三天时间调试二分查找的边界条件最终发现问题的根源在于对循环不变量的理解偏差。这种经历让我意识到算法训练不能停留在ACAccept层面更要理解每个判断条件背后的数学逻辑。下面我就结合这三个经典题目分享如何建立正确的解题思维模式。2. 704. 二分查找深度剖析2.1 算法原理与边界陷阱二分查找看似简单但根据ACM统计90%的程序员无法一次性写出完全正确的实现。核心难点在于处理区间定义和终止条件。我们以升序数组nums [-1,0,3,5,9,12]和target9为例def search(nums, target): left, right 0, len(nums) - 1 # 定义闭区间[left, right] while left right: # 当leftright时区间仍然有效 mid left (right - left) // 2 # 防止溢出 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # 目标在右区间 else: right mid - 1 # 目标在左区间 return -1关键点解析区间定义决定边界处理闭区间意味着right初始值为len(nums)-1循环条件leftright保证最后剩余一个元素时仍能检查mid计算使用left(right-left)//2避免(leftright)可能导致的整数溢出常见错误将while条件写成leftright会导致漏查边界元素特别是在查找首尾元素时2.2 变种问题实战二分查找有超过20种变种题型训练营应该重点掌握以下三种查找第一个等于target的元素while left right: mid left (right - left) // 2 if nums[mid] target: right mid - 1 else: left mid 1 return left if nums[left] target else -1查找最后一个等于target的元素while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return right if nums[right] target else -1查找第一个大于等于target的元素while left right: mid left (right - left) // 2 if nums[mid] target: right mid - 1 else: left mid 1 return left每种变种对应的判断条件和返回值都有微妙差异建议在代码中用注释明确标注不变量的定义。3. 27. 移除元素的双指针技法3.1 暴力解法与优化空间最直观的解法是发现目标值后将后续所有元素前移def removeElement(nums, val): i 0 n len(nums) while i n: if nums[i] val: for j in range(i1, n): nums[j-1] nums[j] n - 1 else: i 1 return n时间复杂度O(n²)在LeetCode上会超时这引出了双指针的优化方案。3.2 快慢指针的精妙配合快指针扫描数组慢指针标记有效位置def removeElement(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow这个实现有几个值得注意的细节快指针fast总是比slow快一步或同步赋值操作nums[slow]nums[fast]保证了原地修改最终slow的值就是新数组长度实测技巧当val出现频率低时可以用交换代替赋值来减少写操作次数4. 977. 有序数组的平方的三种解法4.1 暴力排序法及其局限最直接的方法是先平方后排序def sortedSquares(nums): return sorted(x*x for x in nums)时间复杂度O(nlogn)虽然能通过但未利用输入数组已排序的特性。4.2 双指针的逆向思维利用原数组有序的特性最大值只可能出现在两端def sortedSquares(nums): n len(nums) result [0] * n left, right 0, n - 1 for i in range(n-1, -1, -1): if abs(nums[left]) abs(nums[right]): result[i] nums[left] ** 2 left 1 else: result[i] nums[right] ** 2 right - 1 return result这个解法体现了几个重要思维结果数组从后往前填充避免额外空间交换比较绝对值而非实际值处理负数情况时间复杂度优化到O(n)4.3 边界条件测试用例验证算法时需要特别考虑这些情况全负数数组[-4,-3,-2,-1]全正数数组[1,2,3,4]零值数组[0,0,0]混合数组[-3,-1,0,2,5]5. 算法训练的方法论建议5.1 刷题三遍法实践根据代码随想录推荐的方法我改良出自己的三遍刷题法第一遍限时15分钟独立解题记录初始思路第二遍查看题解后重写标注与优秀解法的差距第三遍隔天后白板编程重点训练边界条件处理5.2 调试日志的重要性在二分查找调试时建议添加临时日志print(fL{left}, R{right}, M{mid}, nums[M]{nums[mid]})这能清晰展示搜索区间变化过程快速定位边界错误。5.3 复杂度分析的实操技巧不要死记公式建议根据循环结构直观判断单层循环通常是O(n)嵌套循环看乘积关系双重循环可能是O(n²)递归算法画调用树深度乘以每层操作数6. 常见错误与调试实录6.1 二分查找的死循环陷阱当出现死循环时检查三个关键点区间更新是否至少缩小1mid±1循环条件是否允许leftright的情况mid计算是否可能陷入无限取整6.2 数组索引越界防护在操作数组时务必进行前置检查if not nums: return 0 if index len(nums): raise IndexError6.3 双指针的同步问题快慢指针类题目常见错误模式指针移动条件错误该移动时未移动指针初始位置不当应从同一起点开始终止条件遗漏边界情况7. 性能优化与测试策略7.1 LeetCode提交时的优化技巧在函数开始处添加极端条件判断使用内置函数替代手动循环如max()避免不必要的临时变量创建7.2 自定义测试用例设计建议按以下比例构造测试集30%常规情况30%边界条件20%极端案例20%随机生成例如对移除元素题目应该包含空数组全部元素都需要移除首尾元素需要移除连续多个需要移除的元素8. 从这三个题目看算法思维这三个题目虽然简单但蕴含了算法设计的核心思想二分查找体现分治思想双指针展示如何优化多重循环平方排序题演示了问题转化的技巧我在面试候选人时发现能清晰解释这三个题目背后思维逻辑的开发者通常具有更扎实的算法基础。建议在训练营期间每个题目都尝试用不同方法实现并比较它们的优劣。
1. 算法训练营开营二分查找与数组操作实战第一次参加算法训练营的学员往往会对数组基础操作感到既熟悉又陌生。熟悉是因为数组作为最基本的数据结构几乎出现在所有编程语言中陌生则是因为在实际解题时总会出现各种边界条件问题。今天的三个题目——704二分查找、27移除元素和977有序数组的平方恰好构成了数组操作的铁三角查找、删除和转换。我在刷题初期曾花费整整三天时间调试二分查找的边界条件最终发现问题的根源在于对循环不变量的理解偏差。这种经历让我意识到算法训练不能停留在ACAccept层面更要理解每个判断条件背后的数学逻辑。下面我就结合这三个经典题目分享如何建立正确的解题思维模式。2. 704. 二分查找深度剖析2.1 算法原理与边界陷阱二分查找看似简单但根据ACM统计90%的程序员无法一次性写出完全正确的实现。核心难点在于处理区间定义和终止条件。我们以升序数组nums [-1,0,3,5,9,12]和target9为例def search(nums, target): left, right 0, len(nums) - 1 # 定义闭区间[left, right] while left right: # 当leftright时区间仍然有效 mid left (right - left) // 2 # 防止溢出 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # 目标在右区间 else: right mid - 1 # 目标在左区间 return -1关键点解析区间定义决定边界处理闭区间意味着right初始值为len(nums)-1循环条件leftright保证最后剩余一个元素时仍能检查mid计算使用left(right-left)//2避免(leftright)可能导致的整数溢出常见错误将while条件写成leftright会导致漏查边界元素特别是在查找首尾元素时2.2 变种问题实战二分查找有超过20种变种题型训练营应该重点掌握以下三种查找第一个等于target的元素while left right: mid left (right - left) // 2 if nums[mid] target: right mid - 1 else: left mid 1 return left if nums[left] target else -1查找最后一个等于target的元素while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return right if nums[right] target else -1查找第一个大于等于target的元素while left right: mid left (right - left) // 2 if nums[mid] target: right mid - 1 else: left mid 1 return left每种变种对应的判断条件和返回值都有微妙差异建议在代码中用注释明确标注不变量的定义。3. 27. 移除元素的双指针技法3.1 暴力解法与优化空间最直观的解法是发现目标值后将后续所有元素前移def removeElement(nums, val): i 0 n len(nums) while i n: if nums[i] val: for j in range(i1, n): nums[j-1] nums[j] n - 1 else: i 1 return n时间复杂度O(n²)在LeetCode上会超时这引出了双指针的优化方案。3.2 快慢指针的精妙配合快指针扫描数组慢指针标记有效位置def removeElement(nums, val): slow 0 for fast in range(len(nums)): if nums[fast] ! val: nums[slow] nums[fast] slow 1 return slow这个实现有几个值得注意的细节快指针fast总是比slow快一步或同步赋值操作nums[slow]nums[fast]保证了原地修改最终slow的值就是新数组长度实测技巧当val出现频率低时可以用交换代替赋值来减少写操作次数4. 977. 有序数组的平方的三种解法4.1 暴力排序法及其局限最直接的方法是先平方后排序def sortedSquares(nums): return sorted(x*x for x in nums)时间复杂度O(nlogn)虽然能通过但未利用输入数组已排序的特性。4.2 双指针的逆向思维利用原数组有序的特性最大值只可能出现在两端def sortedSquares(nums): n len(nums) result [0] * n left, right 0, n - 1 for i in range(n-1, -1, -1): if abs(nums[left]) abs(nums[right]): result[i] nums[left] ** 2 left 1 else: result[i] nums[right] ** 2 right - 1 return result这个解法体现了几个重要思维结果数组从后往前填充避免额外空间交换比较绝对值而非实际值处理负数情况时间复杂度优化到O(n)4.3 边界条件测试用例验证算法时需要特别考虑这些情况全负数数组[-4,-3,-2,-1]全正数数组[1,2,3,4]零值数组[0,0,0]混合数组[-3,-1,0,2,5]5. 算法训练的方法论建议5.1 刷题三遍法实践根据代码随想录推荐的方法我改良出自己的三遍刷题法第一遍限时15分钟独立解题记录初始思路第二遍查看题解后重写标注与优秀解法的差距第三遍隔天后白板编程重点训练边界条件处理5.2 调试日志的重要性在二分查找调试时建议添加临时日志print(fL{left}, R{right}, M{mid}, nums[M]{nums[mid]})这能清晰展示搜索区间变化过程快速定位边界错误。5.3 复杂度分析的实操技巧不要死记公式建议根据循环结构直观判断单层循环通常是O(n)嵌套循环看乘积关系双重循环可能是O(n²)递归算法画调用树深度乘以每层操作数6. 常见错误与调试实录6.1 二分查找的死循环陷阱当出现死循环时检查三个关键点区间更新是否至少缩小1mid±1循环条件是否允许leftright的情况mid计算是否可能陷入无限取整6.2 数组索引越界防护在操作数组时务必进行前置检查if not nums: return 0 if index len(nums): raise IndexError6.3 双指针的同步问题快慢指针类题目常见错误模式指针移动条件错误该移动时未移动指针初始位置不当应从同一起点开始终止条件遗漏边界情况7. 性能优化与测试策略7.1 LeetCode提交时的优化技巧在函数开始处添加极端条件判断使用内置函数替代手动循环如max()避免不必要的临时变量创建7.2 自定义测试用例设计建议按以下比例构造测试集30%常规情况30%边界条件20%极端案例20%随机生成例如对移除元素题目应该包含空数组全部元素都需要移除首尾元素需要移除连续多个需要移除的元素8. 从这三个题目看算法思维这三个题目虽然简单但蕴含了算法设计的核心思想二分查找体现分治思想双指针展示如何优化多重循环平方排序题演示了问题转化的技巧我在面试候选人时发现能清晰解释这三个题目背后思维逻辑的开发者通常具有更扎实的算法基础。建议在训练营期间每个题目都尝试用不同方法实现并比较它们的优劣。
