1. Two Sum

Leetcode

https://leetcode.com/problems/two-sum

題目

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]

解答

• 方法一

雙層迴圈硬解

var twoSum = function(nums, target) {
    for(let i=0; i<nums.length; i++) {
        for(let j=i+1; j<nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
};

Runtime: 96 ms Beats 37.93% of users with JavaScript

Memory: 49.64 MB Beats 30.19% of users with JavaScript

• 方法二

一層迴圈 + Hash Table

var twoSum = function(nums, target) {
    const map = new Map();

    for(let i=0; i<nums.length; i++) {
        const value = nums[i];
        const hashKey = target - value;
        if (map.has(hashKey)) {
            return [map.get(hashKey), i];
        }
        map.set(value, i);
    }
};

Runtime: 56 ms Beats 81.99% of users with JavaScript

Memory: 51.86 MB Beats 6.83% of users with JavaScript

參考資料

https://ithelp.ithome.com.tw/articles/10269246