leetcode 2sum 思考流程

def 2sum():
   for i in range(len(list1)):
      for j in range(len(list1)):
         if list1[i] + list1[j+1] == target 
            

第一個有趣的地方是我要加他後面的那個index裡面的值，不需要比自己所以我想往後加，不過最後他會out of range, 因為沒有沒有最後一個+1的index @@
這該怎麼辦呢?

網路上用這這個方式

left = nums[i+1:] 每次都產生一個list不包含自己，本來覺得好像很佔空間 不過好像就是多一個n的空間，每次都會更新 看看有沒有其他方法

結果其實內建就有這個辦法了好嗎XD
range(開始,結束,step) 所以只要在第二個loop裡面每次都從i+1開始

def 2sumPoorWay(list, target):
   for i in range(len(list)):
      for j in range(i+1, len(list)):
         if list[i] + list[j] == target :
            return list(i, j)

對於直接回傳list有點遲疑，是這樣用嗎? > 不是，會報錯list()裡面只是把東西變成list type QQ

正確就是直接 return [i, j] 但這是爛方法 O(n^2) 熱身一下而已

def 2SumBetter(list, target):
   dict1 = {}
   for i in range(len(list)):
      j = target - list[i]
      if j in dict1:
         return [i, dict1[j]]
      else:
         dict1[list[j], j] 卡住
         

建立dict的方式也是一門藝術～ 要直接查表就是把index當作value超衝突
用if xxx in dict的時候預設是去比對index

完蛋 忘記怎樣加入dict = = > dict1[i] = list1[i] 好蠢喔

def 2SumBetter(list, target):
   dict1 = {}
   rest = 0
   for i in range(len(list)):
      rest = target - list[i]
      if rest in dict1:
         return [i, dict1[rest]]
      else:
         dict1[rest] = i

看起來好像對了 但是要用example去跑一下
[2,7,3,1] target = 9 :
i = 0, list[0] = 2, rest = 9 – 2 = 7, 7 is not in dict1, dict1[7]=0
i = 1, list[1] = 7, rest = 9 – 7 = 2, 2 is in dict1, dict1 = {7:0}, return [1, 0]

想一下corner case ? 題目說一定有答案 就不會是空的
丟去leetcode跑看看

結果是錯的 出來答案竟然是空的QQ 咁我到底在跑啥鬼
dict1[rest] = i 根本就是錯的 要加入字典是自己本身，讓後面未來的人可以查
而不是加入我想要的，因為想要的下次就不一樣了啊～

然後再想想為何我的run code沒看出錯誤 2 根本不在裡面 根本存錯，存7…

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict1 = {}
        rest = 0
        for i in range(len(nums)):
            rest = target - nums[i]
            #print(rest)
            if rest in dict1:
                return [i, dict1[rest]]
            else:
                dict1[nums[i]] = i
                #print(dict1)