Python面试30分钟突击掌握-LeetCode1-Array

Python 面试 30 分钟突击掌握LeetCode 第一篇Array如果你正在准备 Python 开发岗面试时间又不多这篇文章就是为你准备的。很多同学刷题时容易陷入两个误区只看答案不自己推导只记代码不理解“为什么这样做”。面试官真正想看到的不是你背过多少题而是你是否具备拆解问题、选择结构、评估复杂度、清晰表达的能力。数组Array题目恰好是这四项能力最常见的考察入口。为什么先练 Array在真实面试中Array 是出镜率极高的题型原因很简单数组是最基础的数据结构几乎所有业务代码都会接触可以自然延伸到哈希表、双指针、滑动窗口、前缀和等高频技巧易于从“简单题”问到“进阶优化题”非常适合面试追问。如果你只有 30 分钟建议先把以下两题吃透Single NumberTwo Sum这两题覆盖了面试中的两类核心思路位运算消重和哈希换时间。今天的突击目标你不需要一口气刷很多题只要做到这四点能在不看答案的前提下写出 AC 代码能说清楚时间复杂度和空间复杂度能解释为什么这个解法优于朴素解法能描述常见边界条件和易错点。题目一Single Number只出现一次的数字题目描述给定一个非空整数数组nums除了某个元素只出现一次以外其余每个元素都出现两次。请找出那个只出现一次的元素。要求时间复杂度为线性级别O(n)额外空间复杂度为常数级别O(1)。示例输入[2,2,1]输出1输入[4,1,2,1,2]输出4输入[1]输出1面试中的思考路径很多人第一反应是“排序后相邻比较”这能做出来但复杂度是O(n log n)不满足线性要求。也有人想到用哈希计数时间是O(n)但空间是O(n)不满足常数空间要求。这时你要主动向面试官表达题目同时要求O(n)时间和O(1)空间通常在暗示位运算XOR。关键知识异或 XOR异或有三个特别有用的性质a ^ a 0相同数字异或为 0a ^ 0 a任何数字与 0 异或还是自己满足交换律和结合律顺序不影响结果因此数组里成对出现的数字最终都会被“抵消”只剩下那个只出现一次的数字。Python 参考实现fromtypingimportListclassSolution:defsingleNumber(self,nums:List[int])-int:result0forvalueinnums:result^valuereturnresult复杂度分析时间复杂度O(n)遍历一次数组空间复杂度O(1)只用了一个变量。面试易错点忘记解释“为什么是O(1)空间”只给代码不给位运算性质推导把异或写成了按位或|或按位与。题目二Two Sum两数之和题目描述给定一个整数数组nums和一个目标值target请返回两个数的下标使它们之和等于target。约束条件每种输入只会对应一个有效答案同一个元素不能重复使用返回下标顺序不限。示例nums [2,7,11,15], target 9返回[0,1]nums [3,2,4], target 6返回[1,2]nums [3,3], target 6返回[0,1]面试中的思考路径朴素做法是双重循环复杂度O(n^2)。题目 follow-up 会问能否优于O(n^2)这个追问基本就是在引导你使用哈希表字典遍历当前值value计算补数need target - value看need是否已经在哈希表中如果在直接返回对应下标和当前下标如果不在把当前值和下标存入哈希表继续遍历。Python 参考实现fromtypingimportListclassSolution:deftwoSum(self,nums:List[int],target:int)-List[int]:index_map{}fori,valueinenumerate(nums):needtarget-valueifneedinindex_map:return[index_map[need],i]index_map[value]ireturn[]复杂度分析时间复杂度O(n)每个元素只处理一次空间复杂度O(n)最坏情况下哈希表存下所有元素。面试易错点先把当前值放入哈希表再查补数导致某些场景下错误复用自己只会写代码不会解释“为什么哈希可以把两层循环降成一层”遇到重复元素如[3,3]时思路混乱。30 分钟高效练习法推荐如果你现在就要突击按这个节奏走5 分钟看题 口述思路先别写代码10 分钟独立手写Single Number和Two Sum10 分钟对照复杂度、边界条件优化表达5 分钟脱稿复述像在真实面试中那样讲给别人听你会发现真正拉开差距的不是“会不会”而是“能不能讲清楚”。面试表达模板可直接套用你可以这样说这题我先考虑朴素解法时间复杂度是O(n^2)。由于题目追求更优复杂度我会用哈希表把查找从线性降到常数平均时间整体优化到O(n)。空间上会增加到O(n)这是典型的空间换时间。我还会注意重复元素和不能复用同一元素这两个边界约束。这段表达对Two Sum非常加分也能迁移到很多类似题目。小结Array 是面试高频中的高频Single Number和Two Sum是你必须拿下的基础分。请记住刷题不是背答案而是训练你在压力下快速建立正确解法并清晰表达。如果你把本文两题做到下面这个标准面试通过率会明显提升代码能在白板/在线编辑器中一次写对复杂度能张口即来追问“还能更优吗”时不慌能讲出方法选择背后的理由。下一步你可以继续进入 Array 进阶题双指针、滑动窗口和前缀和。把这条主线打通你在 Python 开发岗面试中的算法表现会稳定很多。