LeetCode 001 两数之和

有勇气的牛排 29 算法 2025-08-03 22:57:35

程序员兼职接单交流

编程交流

进群口令：博客

题目

知识点：数组、哈希表

给定一个整数数组 nums 和一个整数目标值 target，请你再该数组中找出 和为目标值 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]

提示：

2 <= nums.length <= 104
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

暴力枚举（双层循环）

思路：枚举数组中所有可能的两两组合，检查它们的和是否等于target。

时间复杂度：O(n²)

空间复杂度：O(1)

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                print(i, j)
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []


print(Solution().twoSum([2, 7, 11, 15], 9))  # [0, 1]
print(Solution().twoSum([3, 2, 4], 6))       # [1, 2]
print(Solution().twoSum([3, 3], 6))          # [0, 1]

组合

哈希表（一次遍历）

思路：

使用字典（哈希表）存储已经遍历过的数字及其下标。
每次遍历一个数 num，计算它需要的补数，complement = target - num
如果补数在哈希表中，说明找到了答案

时间复杂度：O(n)

空间复杂度：O(n)

# -*- coding: utf-8 -*-
from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        lookup = {}

        for index, num in enumerate(nums):
            complement = target - num
            print(index, num, complement)

            if complement in lookup:
                # 补数在已经遍历过的记录中存在
                return [lookup[complement], index]
            else:
                # 不存在则添加记录，并记录索引
                lookup[num] = index

        return []

print(Solution().twoSum([2, 7, 11, 15], 9))  # [0, 1]
print(Solution().twoSum([3, 2, 4], 6))       # [1, 2]
print(Solution().twoSum([3, 3], 6))          # [0, 1]

一句话描述：

哈希记录已遍历元素+下标，后面元素如果补数匹配到前面结果，即成功。

<h2><a id="_0"></a>题目</h2> 知识点：数组、哈希表 给定一个整数数组 <code>nums</code> 和一个整数目标值 <code>target</code>，请你再该数组中找出 和为目标值 <code>target</code> 的那两个整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案，并且你不能使用两次想同的元素。 你可以按任意顺序返回答案。 示例1： <blockquote> 输入：nums = [2, 7, 11, 15], target=9 输出：[0, 1] 解释：因为 nums[0] + nums[1] == 9，返回[0, 1] </blockquote> 示例2: <blockquote> 输入：nums = [3, 2, 4]，target = 6 输出[1, 2] </blockquote> 示例3： <blockquote> 输入：nums = [3, 3]，target = 6 输出：[0, 1] </blockquote> 提示： <ul> <li><code>2 <= nums.length <= 104</code></li> <li><code>-10^9 <= nums[i] <= 10^9</code></li> <li><code>-10^9 <= target <= 10^9</code></li> <li>只会存在一个有效答案</li> </ul> <h2><a id="_37"></a>暴力枚举（双层循环）</h2> 思路：枚举数组中所有可能的两两组合，检查它们的和是否等于<code>target</code>。 时间复杂度：O(n²) 空间复杂度：O(1) <pre><div class="hljs"><code class="lang-python">from typing import List class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: n = len(nums) for i in range(n): for j in range(i + 1, n): print(i, j) if nums[i] + nums[j] == target: return [i, j] return [] print(Solution().twoSum([2, 7, 11, 15], 9)) # [0, 1] print(Solution().twoSum([3, 2, 4], 6)) # [1, 2] print(Solution().twoSum([3, 3], 6)) # [0, 1] </code></div></pre> 组合 <pre><div class="hljs"><code class="lang-shell">0 1 0 2 0 3 1 2 1 3 2 3 </code></div></pre> <h2><a id="_76"></a>哈希表（一次遍历）</h2> 思路： <ol> <li>使用字典（哈希表）存储已经遍历过的数字及其下标。</li> <li>每次遍历一个数 num，计算它需要的补数，<code>complement = target - num</code></li> <li>如果补数在哈希表中，说明找到了答案</li> </ol> 时间复杂度：O(n) 空间复杂度：O(n) <pre><div class="hljs"><code class="lang-python"># -*- coding: utf-8 -*- from typing import List class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: lookup = {} for index, num in enumerate(nums): complement = target - num print(index, num, complement) if complement in lookup: # 补数在已经遍历过的记录中存在 return [lookup[complement], index] else: # 不存在则添加记录，并记录索引 lookup[num] = index return [] print(Solution().twoSum([2, 7, 11, 15], 9)) # [0, 1] print(Solution().twoSum([3, 2, 4], 6)) # [1, 2] print(Solution().twoSum([3, 3], 6)) # [0, 1] </code></div></pre> 一句话描述： 哈希记录已遍历元素+下标，后面元素如果补数匹配到前面结果，即成功。

LeetCode 001 两数之和

题目

暴力枚举（双层循环）

哈希表（一次遍历）

评论区