題目描述

給一個列表以及一個列表裡兩數相加起來的數，返回此兩數的列表位置

解題思路

  1. 可用字典結構當作存取位置用，並用遍歷將相減後還沒有出現的數存進字典裡，之後如果有遍歷到字典裡的數即可立馬返回位置

  2. 一樣使用雙指針，將list的index跟element分組做排序，因此新的list為由小到大，接著使用雙指針，一個指向頭一個指向尾，相加如果小於target則代表start太小，相加如果大於target代表end太大

Python

原本想用兩個for去解決

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            left = nums[i+1:]
            for j in range(len(left)):
                if (nums[i] + left[j]) == target:
                    return i, j+i+1

但提交後噴了time limit exceeded

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}

        for i in range(len(nums)):
            if target - nums[i] not in dict:
                dict[nums[i]] = i
            else:
                return [dict[target - nums[i]], i]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        list_ele_idx = [(ele, idx) for idx, ele in enumerate(nums)] # 主要讓ele在前，使sort生效，因此前面會寫成(ele, idx)，讓ele可以排序
        list_ele_idx.sort()

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