Leetcode 紀錄 - Two sum

Two sum

在這個問題中會得到一個 target 和一個 array ，而 target 一定會是 array 中兩的數值的合，

我們要找出那兩個數值在 array 中的位置，然後還要符合時間複雜度。

坦白說我覺得滿難的ＱＱ.... 實在是沒怎麼想過這類問題。希望可以越寫越熟拉 哈哈

總之，我自己是寫了兩個解法，感覺是很標準的那種沒什麼特別的就是了，

第一種是不管時間複雜度，直接暴力給他跑兩個 for，重點在於當第一個數值進來的時候會掃一次所以其他在 array 中的值直到找到另一個值相加等於 target 時就結束。

Python :

class Solution:
    def twoSum(self, nums, target: int) -> int:
        result_list=[]
        for nums_index in range(len(nums)) :
            for num_t in  range(len(nums)) :
                if  num_t != nums_index > 0 and nums[nums_index] + nums[num_t] == target :
                    print(nums[nums_index] ,nums[num_t])
                    result_list.append(nums_index)
                    result_list.append(num_t)                               
                    return result_list
        
nums = [7,3,9,3,78,8]
print(Solution.twoSum(Solution,nums,6))

另一個作法是只要一個 for 就好，時間複雜度是符合解題許可範圍的，但不是最佳解就是了。

總之，另一個作法會要先知道 python dictionary 的一些特性與用法就可以解了，

(當初不知道就想很久....有看到說可以用 key-value pairs 就會了XD)

Python :

class Solution:
	def twoSum(self, nums, target: int) -> int:
        result_dict = {}
        for nums_index in range(len(nums)) :
            print('nums index : ',nums_index)
            t_nums1 = nums[nums_index] 
            t_nums2 = target - t_nums1
            print(t_nums1)
            if t_nums2 in result_dict :  
                return [result_dict[t_nums2],nums_index]   
            result_dict[t_nums1] = nums_index
            # 流程上就是一個一個數值都跑一次 , 每跑一次不符合條件就直接依序加到 dict 中
nums = [7,3,9,3,78,8]
print(Solution.twoSum(Solution,nums,6))

裡面的 if 條件就是一直 try 到有 t_nums2 的值在 result_dict 中就會知道是第幾個了, 也會知道目前是在處理哪一個值。所以當有符合這個條件的時候就會回傳答案出來了。