两数之和

Tips

题目类型: HashMap

题目

给你一个数组 nums 和一个整数 target, 数组中保证存在两个数的和为 target, 请你返回这两个数的索引.

提示:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• 只会存在一个有效答案

示例

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

输入: (nums = [3, 2, 4]), (target = 6)
输出: [1, 2]

输入: (nums = [3, 3]), (target = 6)
输出: [0, 1]

题解

创建一个哈希表, 遍历数组, 将元素存储到哈希表中, 如果 target - nums[i] 存在于哈希表中, 那么就找到了这两个相加等于 target 的元素.

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const n = nums.length
  const map = new Map()

  for (let i = 0; i < n; i++) {
    const complement = target - nums[i]

    if (map.has(complement)) {
      return [map.get(complement), i]
    }

    map.set(nums[i], i)
  }
}

Rust

use std::collections::HashMap;

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut map = HashMap::new();

    for (i, num) in nums.iter().enumerate() {
        let complement = target - num;

        if let Some(x) = map.get(&complement) {
            return vec![*x, i as i32];
        }

        map.insert(*num, i as i32);
    }

    vec![]
}

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)