1 - 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]

Constraints:

2 <= nums.length <= 104
109 <= nums[i] <= 109
109 <= target <= 109
Only one valid answer exists.

Follow-up:

Can you come up with an algorithm that is less than O(n2) time complexity?

中文題解

給予一個輸入陣列和一個目標數值，在陣列中找到兩個值的和加起來等於目標數值，回傳兩值在陣列中的 index。

題目向我們保證只會有一組答案所以不必擔心會找不到答案或是有多個答案。

方法1

最爲簡單的方法是搜尋每個值的組合加起來看看能不能找到目標（暴力解）

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

方法2

以 nums = [2, 7, 11, 15], target = 9 爲例

注意每個數字，例如 2，我們需要找的是 2 與 target 之間的差（abs(2 - 9) = 7），7 是唯一能夠與 2 相加等於目標 9 的數值，因此我們不需要檢查每個數字，我們只需知道 7 是否存在。

function twoSum(nums: number[], target: number): number[] {
    const counter = {};
    
    for (const [index, val] of nums.entries()) {
        const diff = target - val
        if (diff in counter) {
            return [counter[diff], index]
        }
        else {
            counter[val] = index
        }
    }
};