Easy

题目描述

给定一个整数数组 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 <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案

进阶： 你可以想出一个时间复杂度小于 O(n²) 的算法吗？

解题思路

这道题有两种主要解法：

方法一：暴力解法 最直观的解法是使用两层循环，对于每个数字，遍历后面的所有数字，检查两数之和是否等于目标值。虽然简单易懂，但时间复杂度为 O(n²)，在数据量大时效率较低。

方法二：哈希表（推荐解法） 我们可以利用哈希表来优化算法。遍历数组时，对于当前元素 nums[i]，我们需要查找是否存在一个数字 target - nums[i]。如果存在且不是同一个位置，那么就找到了答案。

具体流程：

  1. 创建一个哈希表，用于存储数字和其对应的索引
  2. 遍历数组，对于每个元素：
    • 计算补数 complement = target - nums[i]
    • 检查补数是否已存在于哈希表中
    • 如果存在，返回当前索引和补数的索引
    • 如果不存在，将当前数字和索引存入哈希表

这种方法只需要一次遍历，时间复杂度为 O(n)，是最优解法。

代码实现

class Solution {
public:
    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.find(complement) != map.end()) {
                return {map[complement], i};
            }
            map[nums[i]] = i;
        }
        return {};
    }
};

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        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 []

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        Dictionary<int, int> map = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            int complement = target - nums[i];
            if (map.ContainsKey(complement)) {
                return new int[] {map[complement], i};
            }
            map[nums[i]] = i;
        }
        return new int[0];
    }
}

var twoSum = function(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表解法暴力解法
时间复杂度O(n)O(n²)
空间复杂度O(n)O(1)

说明：

  • 时间复杂度：哈希表解法只需遍历一次数组，每次哈希表操作为 O(1)，总体为 O(n)
  • 空间复杂度：哈希表解法需要额外的哈希表存储空间，最坏情况下为 O(n)

相关题目