[LeetCode] 1. Two Sum

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]

Github Solution

#time:O(n),  space:O(n)
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return
        table = {}
        for idx, num in enumerate(nums):
            remain = target - num
            if remain in table:
                return [table[remain], idx]
            table[num] = idx
        return []

Solution:

1. using a hash table to memorize each number and its corresponding index while traversing this list
2. traverse this list. If the remain which is (target – this number) is in this hash table, meaning that (remain + this number) is equal to target. Then, return the index of remain checked from the hash table and the index of this number as a list.
3. If (remain + this number) is not equal to target. Store this number as a key in the hash table and its index as a value.

解法：

1. 用hash table紀錄number跟其對應的index
2. 遍歷number list, 在每個number時，先拿target減去number成remain，看hash table裡有沒有remain，有就return remain對應的index跟此number的index
3. 沒有就把此number當作key，其index當作value塞進hash_table