[Leetcode]1 : Two Sum

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

Problem :
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.

圖來自leetcode

Thoughts :
1. 一開始沒有想到要用enumerate，可以同時取用到 key 跟 value。
2. 跑迴圈，並透過與target相減的方式來獲得需要的資訊。
3.在return的時候需要注意如何取得 key。

Solution :

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #拿來暫存而已
        dic = {}
        #開始跑key,value
        for i, j in enumerate(nums):
            #計算相減後的值
            tmp = target - j
            #如果j值沒有在裡面，把值放進去dic裡面
            if j not in dic.keys():
                dic[tmp] = i
            #return值
            else:
                return [dic.get(j),i]

time complexity, space complexity

follow up question:
1-陣列是否排序好了？
2-是否會有多組解答？
3-是否會有重複的數字？
4-worse case?