項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Leetcode】python – [1] Two Sum 個人解法筆記 (updated: 2022/04/06) | 內有 list comprehesion / dict comprehesion 整理

題目出處

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

難度

Easy

個人範例程式碼 – 三刷 (2022/04/06)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        list_number_and_index = [(ele, idx) for idx, ele in enumerate(nums)]
        list_number_and_index.sort()

        start, end = 0, len(nums)-1   
        while(start < end):
            if list_number_and_index[start][0] + list_number_and_index[end][0] == target:
                return sorted([list_number_and_index[start][1], list_number_and_index[end][1]])
            elif list_number_and_index[start][0] + list_number_and_index[end][0] < target: # need bigger
                start += 1
            else: # nums[start] + nums[end] > target: # need smaller
                end -= 1
        else:
            return [-1, -1]

算法說明 – two pointers

這次使用 two pointers 的作法,這個做法的優點是可以比較下表,
基本上就是能節省掉 hashmap 的空間,取而代之的是比較多的時間

空間可以換時間,時間可以換空間。 這個觀念非常的重要!!!

hashmaptwo pointers
空間複雜度O(n)O(1)
時間複雜度O(1)O(n), 但有前置步驟 sort = O(nlogN)

最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解

input handling

處理沒有結果的狀況 [-1, -1]

Boundary conditions

two pointers 循環條件 while(start < end)

補充:list comprehesion

list_number_and_index = [(ele, idx) for idx, ele in enumerate(numbers)]

補充:dict comprehesion

dict_number_to_index = {ele: idx for idx, ele in enumerate(numbers)}

個人範例程式碼 – 二刷 (2022/02/24)

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        mydict = {}
        for idx in range(len(nums)):     
            # print(mydict.keys())       
            if nums[idx] in mydict.keys():
                return [mydict[nums[idx]], idx]
            else:
                mydict[target - nums[idx]] = idx

個人範例程式碼 – 一刷 (2021/03/16)

class Solution:
    def twoSum(self, nums, target): # 2 7 11 15
        my_dict = {}
        for idx, ele in enumerate(nums):
            rest = target - ele
            if rest in my_dict:
                return [my_dict[rest], idx]
            else:
                my_dict[ele] = idx # record

解法 – HashTable

這題主要考的是 HashTable,
需要先建立一張表 (此處建立 dict),
利用 「key -> value」 的特性保存 「剩餘值 對應 index」
因此當後續的計算,發現剩餘值存在 dict 的 key 中,
就能快速反查表得到 index。

示意圖

(將找不到 remain value 的值,作為 key 存進 dict 中)

Reference