「LeetCode」 Two Sum

两数之和

开始学习Python的第一天，努力ing

---

题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出 和为目标值 的那两个整数，并返回它们的数组下标。

• 输入：
  • 数组 nums（长度至少为 2）。
  • 目标值 target。
• 输出：
  • 返回两个数的索引，使得它们的和等于目标值。
• 假设：
  • 每种输入只会对应一个答案。
  • 你不能使用同一个元素两次。

---

示例

示例 1：

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。

示例 2：

输入：nums = [3, 2, 4], target = 6
输出：[1, 2]

示例 3：

输入：nums = [3, 3], target = 6
输出：[0, 1]

---

方法 1：暴力法

实现步骤

1. 使用外层循环固定第一个数的索引 i。
2. 使用内层循环从 i+1 开始，检查后续的所有数。
3. 如果两个数的和等于目标值 target，立即返回它们的索引。
4. 如果遍历结束仍未找到符合条件的两个数，则返回空列表。

Python 实现

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 外层循环固定第一个数
        for i in range(len(nums)):
            # 内层循环从 i+1 开始，避免重复使用元素
            for j in range(i + 1, len(nums)):
                # 检查两数之和是否等于目标值
                if nums[i] + nums[j] == target:
                    # 如果找到，立即返回索引
                    return [i, j]
        # 根据题目假设，这里不会执行到
        return []

示例运行

输入：nums = [2, 7, 11, 15], target = 9

• 外层循环 i = 0，内层循环：
  • j = 1，nums[0] + nums[1] = 2 + 7 = 9，找到答案，返回 [0, 1]。

输入：nums = [3, 2, 4], target = 6

• 外层循环 i = 0，内层循环：
  • j = 1，nums[0] + nums[1] = 3 + 2 = 5，不匹配。
  • j = 2，nums[0] + nums[2] = 3 + 4 = 7，不匹配。
• 外层循环 i = 1，内层循环：
  • j = 2，nums[1] + nums[2] = 2 + 4 = 6，找到答案，返回 [1, 2]。

---

逐行代码解析

1. 定义类和方法

class Solution(object):
    def twoSum(self, nums, target):

• class Solution(object)：定义一个类 Solution，用于组织代码。
• def twoSum(self, nums, target)：定义一个方法 twoSum，接收两个参数：
  • nums：一个列表（数组），例如 [2, 7, 11, 15]。
  • target：目标值，例如 9。

---

2. 外层循环

for i in range(len(nums)):

• range(len(nums))：生成从 0 到 len(nums)-1 的数字序列。
• i：外层循环变量，表示当前固定的第一个数的索引。

这里 len(nums)的值为4,所以 range(len(nums)) 就是0，1，2，3

range(start, stop, step) 是一个内置函数，用于生成一系列整数。它的参数有三个：

start （可选）：序列的起始值，默认为 0。

stop ：序列的结束值（不包括这个值）。

step （可选）：步长，默认为 1。

例如：
for i in range(5):  # 等价于 range(0, 5)
    print(i)
输出：0 1 2 3 4

---

3. 内层循环

for j in range(i + 1, len(nums)):

• range(i + 1, len(nums))：生成从 i+1 到 len(nums)-1 的数字序列。
• j：内层循环变量，表示第二个数的索引。
• 注意：从 i+1 开始，确保不会重复使用同一个元素。

---

4. 检查条件

if nums[i] + nums[j] == target:

• nums[i] 和 nums[j]：分别表示数组中索引为 i 和 j 的元素。
• nums[i] + nums[j] == target：检查这两个数的和是否等于目标值。

---

5. 返回结果

return [i, j]

• [i, j]：如果找到符合条件的两个数，返回它们的索引。
• return：结束函数并返回结果。

---

6. 默认返回空列表

return []

• 如果没有找到符合条件的两个数，返回一个空列表 []。
• 根据题目假设，这种情况不会发生。

---

方法 2：哈希表方法

思路

哈希表方法是一种更高效的解决方案。它的核心思想是利用一个字典（哈希表）来存储已经访问过的数字及其索引。在遍历数组的过程中，对于当前数字 num，计算它的补数 complement = target - num，然后检查补数是否已经在哈希表中。如果存在，则找到了两个数；否则，将当前数字存入哈希表。

实现步骤

1. 创建一个空字典 num_to_index，用于存储已访问的数字及其索引。
2. 遍历数组，对于每个数字 num：
   • 计算补数 complement = target - num。
   • 检查补数是否已经在字典中：
     • 如果存在，则返回补数的索引和当前数字的索引。
     • 如果不存在，则将当前数字及其索引存入字典。
3. 根据题目假设，一定会找到答案，因此不需要处理找不到的情况。

Python 实现

class Solution:
    def twoSum(self, nums, target):
        # 创建一个哈希表用于存储已访问的元素及其索引
        num_to_index = {}
        
        # 遍历数组
        for i, num in enumerate(nums):
            # 计算需要的另一个数
            complement = target - num
            
            # 检查这个数是否已经在哈希表中
            if complement in num_to_index:
                # 如果找到，返回结果
                return [num_to_index[complement], i]
            
            # 否则，将当前数和其索引存入哈希表
            num_to_index[num] = i
        
        return []  # 根据题目假设，这里不会执行到

示例运行

输入：nums = [2, 7, 11, 15], target = 9

• 第一步：num = 2, complement = 9 - 2 = 7，哈希表为空，存入 {2: 0}。
• 第二步：num = 7, complement = 9 - 7 = 2，发现 2 在哈希表中，返回 [0, 1]。

输入：nums = [3, 2, 4], target = 6

• 第一步：num = 3, complement = 6 - 3 = 3，哈希表为空，存入 {3: 0}。
• 第二步：num = 2, complement = 6 - 2 = 4，哈希表为 {3: 0}，存入 {3: 0, 2: 1}。
• 第三步：num = 4, complement = 6 - 4 = 2，发现 2 在哈希表中，返回 [1, 2]。

---

逐行代码解析

1. 创建哈希表

num_to_index = {}

• num_to_index：这是一个空字典（哈希表），用于存储已经访问过的数字及其索引。
• 键是数字，值是它的索引。

---

2. 遍历数组

for i, num in enumerate(nums):

• enumerate(nums)：同时获取数组的索引和对应的值。
• i：当前数字的索引。
• num：当前数字的值。

enumerate() 主要用于在遍历可迭代对象（如列表、元组、字符串等）时，同时获取元素的索引和值。它返回一个枚举对象，其中每个元素是一个包含索引和对应值的元组。

enumerate(iterable, start=0)
iterable : 要遍历的可迭代对象（如列表、元组、字符串等）。
start （可选）: 枚举的起始索引，默认为 0。可以通过设置 start 参数来指定从哪个索引开始计数。

例如：
fruits = ['apple', 'banana', 'cherry']

for index, fruit in enumerate(fruits):
    print(f"Index: {index}, Fruit: {fruit}")
    
输出：
Index: 0, Fruit: apple
Index: 1, Fruit: banana
Index: 2, Fruit: cherry

---

3. 计算补数

complement = target - num

• complement：这是我们需要找的“补数”，即 target - num。
• 如果当前数字 num 和某个数字的和等于 target，那么那个数字就是 complement。

---

4. 检查补数是否在哈希表中

if complement in num_to_index:

• complement in num_to_index：检查字典中是否存在键 complement。
• 如果存在，说明我们找到了符合条件的两个数。

---

5. 返回结果

return [num_to_index[complement], i]

• num_to_index[complement]：从字典中取出 complement 对应的索引。
• i：当前数字的索引。
• 返回的是一个包含两个索引的列表。

---

6. 更新哈希表

num_to_index[num] = i

• 如果补数不存在，则将当前数字及其索引存入字典。
• num_to_index[num] = i：将当前数字作为键，索引作为值存入字典。

---

7. 默认返回空列表

return []

• 如果没有找到符合条件的两个数，返回一个空列表 []。
• 根据题目假设，这种情况不会发生。

---