twoSum

1. 两数之和

算法

利用哈希表存储数组元素及其下标：
- 使用一个哈希表，键为数组元素值，值为对应的下标
- 哈希表可以快速查询某个元素是否已经出现过
遍历数组，寻找目标值对应的数：
- 在遍历数组时，对于当前元素 nums[i]，计算另一个需要的数 x = target - nums[i]；
- 在哈希表中检查是否存在 x：
  - 如果 x 存在，说明找到了两个数，返回它们的下标
  - 如果 x 不存在，将当前数 nums[i] 及其索引存入哈希表，继续遍历

复杂度分析

时间复杂度

哈希表查询和插入：每次操作 O(1)
数组遍历：遍历一次数组，时间复杂度为 O(n)
总时间复杂度 O(n)

空间复杂度

需要一个哈希表存储数组中的元素及其索引，空间复杂度为 O(n)

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        std::unordered_map<int, int> hash; // 哈希表存储元素值及其索引

        for (int i = 0; i < nums.size(); ++ i)
        {
            int x = target - nums[i]; // 计算需要的数

            // 检查是否在哈希表中
            if (hash.count(x))
                return {hash[x], i}; // 找到目标值，返回下标

            // 将当前数存入哈希表
            hash[nums[i]] = i;
        }

        return {}; // 如果无解，返回空数组（题目保证一定有解）
    }
};

Python 代码

1
2
3
4
5
6
7
8
9


class Solution:
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    hash_map = {}
    for i, num in enumerate(nums):
      x = target - num
      if x in hash_map:
        return [hash_map[x], i]
      hash_map[num] = i
    return []

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func twoSum(nums []int, target int) []int {
  hash_map := make(map[int]int)
  for i, num := range nums {
    x := target - num
    if idx, ok := hash_map[x]; ok {
      return []int{idx, i}
    }
    hash_map[num] = i
  }
  return []int{}
}

JavaScript 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let hash_map = new Map();
  for (let i = 0; i < nums.length; i++) {
    let x = target - nums[i];
    if (hash_map.has(x)) {
      return [hash_map.get(x), i];
    }
    hash_map.set(nums[i], i);
  }
  return [];
};