LeetCode EP.4

1. Two Sum

Photo by Siora Photography on Unsplash

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]
Output: 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?

思路

一般來說直接暴力解可能會寫兩個For迴圈來解決這題，可能第一次解又在時間受限且時間不夠的當下，但這樣時間複雜度就是 n的平方了。後來看其他人寫的以及我自己嘗試理解後，覺得下面這是最適合我的解法，那要怎麼優化它？

我們專注在讓時間複雜度只有 n 的狀況下，看提示說可以使用HashMap來達成，那在HashMap是空或是找不到匹配的當下我們就把這個數值及位置記下來，那如果相減後的答案匹配的話就會進我們上面的 if 這時就會記下第一次找到的位置與目前數值的位置。

看到這裡也就可以理解為什麼比對的數值要存成 Key 了，為了方便利用它來取值，今天如果把 index 存成 Key 的話就必須要使用迴圈再輪巡一次，這樣就會回到一開始的原點了。

解答

TwoSumSolution

那如果想玩玩看的話也可以參考我的 Github 使用 IntelliJ 就可以 Build 了，裡面也寫了 Test 來驗證。