LeetCode高频面试题：双指针与数组操作实战

1. 算法刷题实战三道经典LeetCode题目精解今天咱们来啃三道高频面试题盛水最多的容器、三数之和、移动零。这三道题分别来自LeetCode的第11、15和283题涵盖了双指针、哈希表、数组操作等核心技巧。我在大厂面试中至少遇到过两次这些题目现在把最实用的解题思路和优化技巧分享给大家。2. LeetCode 11. 盛水最多的容器2.1 问题重述给定一个长度为n的整数数组height找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。示例 输入[1,8,6,2,5,4,8,3,7] 输出49 解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水的最大值为49。2.2 暴力解法分析最直观的解法是双重循环遍历所有可能的组合max_area 0 for i in range(len(height)): for j in range(i1, len(height)): area min(height[i], height[j]) * (j - i) max_area max(max_area, area) return max_area时间复杂度O(n²)在LeetCode上会超时。2.3 双指针优化解法更聪明的做法是使用双指针left, right 0, len(height) - 1 max_area 0 while left right: area min(height[left], height[right]) * (right - left) max_area max(max_area, area) if height[left] height[right]: left 1 else: right - 1 return max_area时间复杂度降为O(n)空间复杂度O(1)。关键点每次移动较矮的指针因为容器的盛水量由较矮的边决定。移动较高的指针不会增加盛水量反而可能减少。2.4 实际面试中的变种面试官可能会问如果数组中有负值怎么办通常题目保证非负如何证明这个贪心策略的正确性可以通过反证法3. LeetCode 15. 三数之和3.1 问题描述给你一个整数数组nums判断是否存在三元组[a,b,c]使得a b c 0找出所有不重复的三元组。示例 输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]]3.2 解题思路先排序O(nlogn)固定一个数转化为两数之和问题使用双指针寻找剩余两个数3.3 完整代码实现def threeSum(nums): nums.sort() res [] for i in range(len(nums)-2): if i 0 and nums[i] nums[i-1]: continue left, right i1, len(nums)-1 while left right: s nums[i] nums[left] nums[right] if s 0: left 1 elif s 0: right - 1 else: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 left 1 right - 1 return res3.4 注意事项去重是关键排序后跳过相同的元素剪枝优化当nums[i] 0时可以直接break因为后面不可能有三数之和为0边界条件数组长度小于3时直接返回空列表4. LeetCode 283. 移动零4.1 问题描述给定一个数组nums将所有0移动到数组的末尾同时保持非零元素的相对顺序。示例 输入[0,1,0,3,12] 输出[1,3,12,0,0]4.2 双指针解法def moveZeroes(nums): slow 0 for fast in range(len(nums)): if nums[fast] ! 0: nums[slow], nums[fast] nums[fast], nums[slow] slow 14.3 算法分析时间复杂度O(n)空间复杂度O(1)类似快排的分区思想把非零元素移到前面4.4 常见错误创建新数组不符合原地修改的要求先删除0再补0时间复杂度变高使用remove(0)每次remove是O(n)操作5. 刷题经验分享5.1 调试技巧对于双指针问题可以在循环中打印指针位置和关键变量使用小规模测试用例如3-5个元素快速验证注意边界条件空数组、全零数组、已排序数组等5.2 面试准备建议每道题至少手写3遍直到能无bug写出准备时间/空间复杂度分析思考可能的follow-up问题5.3 性能对比题目暴力解法最优解法盛水容器O(n²)O(n)三数之和O(n³)O(n²)移动零O(n²)O(n)这三道题都是面试中的高频题目特别是双指针技巧可以解决一大类数组/链表问题。建议先把暴力解法写出来再逐步优化这样面试时即使紧张也能保底。