题目链接

两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

这是一个 核心代码模式 (Core Code Mode) 的题目，你只需要实现 twoSum 函数，无需处理任何输入输出。

示例: 输入:

nums = [0,7,2,1], target = 9

输出:

[1,2]

解释: 因为 nums[1] + nums[2] 等于 9, 所以返回 [1,2]。

解题思路

这是一道非常经典的算法题。

暴力解法: 最直观的方法是使用两层循环。第一层循环枚举第一个数 nums[i]，第二层循环从 i+1 开始枚举第二个数 nums[j]，然后判断它们的和是否等于 target。如果等于，就返回 [i, j]。

  • 时间复杂度:
  • 空间复杂度: 这种方法在数据量较大时会超时。

哈希表法: 我们可以用空间换时间，将时间复杂度优化到 。 核心思想是：在遍历数组时，对于每个元素 x，我们不再向后寻找 target - x，而是反过来思考：之前是否已经遇到过 target - x？

我们可以使用一个哈希表（在C++中是 unordered_map，Java中是 HashMap，Python中是 dict）来存储已经遍历过的数字及其对应的下标。

算法步骤:

  1. 创建一个空的哈希表 map。
  2. 遍历数组 nums，对于每个元素 nums[i]： a. 计算需要的另一个数 complement = target - nums[i]。 b. 在哈希表 map 中查找是否存在键 complement。
    • 如果存在，说明我们找到了解。complement 对应的下标就是 map[complement]，当前数的下标是 i。直接返回 {map[complement], i}。
    • 如果不存在，说明到目前为止还没遇到能和 nums[i] 配对的数。我们将当前的数和它的下标存入哈希表，即 map[nums[i]] = i，以便后续的元素进行查找。

题目保证有唯一解，所以我们总能找到答案。这种方法只遍历数组一次，效率很高。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (map.count(complement)) {
                return {map[complement] + 1, i + 1};
            }
            map[nums[i]] = i;
        }
        return {}; // 题目保证有解，这里是为了编译通过
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement) + 1, i + 1};
            }
            map.put(nums[i], i);
        }
        // 题目保证有解，这里是为了编译通过
        throw new IllegalArgumentException("No two sum solution");
    }
}

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型一维数组
#
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in hash_map:
                return [hash_map[complement] + 1, i + 1]
            hash_map[num] = i
        return [] # 题目保证有解，代码逻辑上不会执行到这里

算法及复杂度

  • 算法: 哈希表
  • 时间复杂度: 。我们只需要遍历一次数组。对于每个元素，哈希表的插入和查找操作的平均时间复杂度都是 。
  • 空间复杂度: 。在最坏的情况下，我们需要将数组中的所有 个元素都存入哈希表中。