1. Two Sum (opens new window)

Description

Difficulty: Easy

Related Topics: Array (opens new window), Hash Table (opens new window)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

**Follow-up: **Can you come up with an algorithm that is less than O(n²) time complexity?

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 方法一：暴力求解
 枚举在数组中所有的不同的两个下标的组合
 逐个检查它们所对应的数的和是否等于target
 
方法一：暴力枚举
思路及算法
​
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
​
当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
​
方法二：哈希表
思路及算法
​
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
​
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。
​
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
​
 */
var twoSum = function(nums, target) {
    const map = {};
    
    for(let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];
        
        if(diff in map) return [i, map[diff]];
        
        map[nums[i]] = i
    }
    
    return []
};
​