力扣 Hot100 攻坚实录：从菜鸟到 Offer 收割机的架构师进阶之路

内容摘要：力扣 Hot100 攻坚实录：从菜鸟到 Offer 收割机的架构师进阶之路,

作为一名拥有十年经验的后端架构师，最近也在重温算法，毕竟面试造火箭，工作拧螺丝。为了帮助更多准备面试的朋友，我决定开始我的 力扣 Hot100 刷题日记，并分享我的解题思路和实战经验，希望能帮助大家在面试中脱颖而出。

面试高频题：两数之和

首先，我们从最经典的题目开始：两数之和。这道题虽然简单，但却是很多面试的敲门砖，考察的是你的基本算法功底和代码编写能力。题目描述是：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

暴力破解与哈希表优化

最容易想到的方法是暴力破解，也就是遍历数组中的每一对元素，看它们的和是否等于目标值。这种方法的时间复杂度是 O(n^2)，效率比较低。更好的方法是使用哈希表，可以将时间复杂度降低到 O(n)。

暴力破解代码示例

def twoSum_brute_force(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

哈希表优化代码示例

def twoSum_hash_table(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

深入理解哈希表

哈希表是一种非常重要的数据结构，它可以在 O(1) 的时间内进行查找、插入和删除操作。在 Python 中，字典 (dict) 就是一种哈希表的实现。哈希表通过将键 (key) 映射到值 (value) 来实现快速查找。当我们使用哈希表解决两数之和问题时，我们可以将数组中的每个元素作为键，将元素的下标作为值存储到哈希表中。然后，对于数组中的每个元素，我们可以在哈希表中查找是否存在一个元素，使得这两个元素的和等于目标值。如果存在，那么我们就找到了答案。

实战避坑经验

1. 边界条件处理：在编写代码之前，一定要考虑清楚各种边界条件，例如数组为空、数组中只有一个元素、目标值不存在等情况。好的习惯是在代码开头进行输入校验，避免程序出现意料之外的错误。例如, 可以加入if not nums: return []来判断输入数组是否为空。
2. 哈希冲突处理：如果使用哈希表，需要注意哈希冲突的问题。虽然 Python 的字典已经处理了哈希冲突，但在其他语言中，可能需要手动处理哈希冲突。常见的哈希冲突解决方法包括链地址法和开放寻址法。
3. 代码可读性：编写清晰易懂的代码非常重要。可以使用有意义的变量名，添加必要的注释，并保持代码的缩进一致。
4. 测试用例覆盖：编写完代码后，一定要编写充分的测试用例，覆盖各种情况，确保代码的正确性。

扩展与思考

两数之和问题可以扩展到 N 数之和问题。例如，三数之和、四数之和等。这些问题都可以使用哈希表或者双指针等方法来解决。但要注意N增大时，时间复杂度也会相应增加，要考虑算法的效率。以后有机会我也会分享这些问题的解题思路。

希望我的 力扣 Hot100 刷题日记能帮助你在面试中取得好成绩！