[leetcode algorithms]題目1

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

自己寫的代碼：

是將數據和對應的下標組成二維數組排序，並過濾出不可能的值。比如最小值-2，目標值是6，那麼大於8的數據就應該被過濾掉。遍歷篩選後的數組進行查找，並pop被遍歷的值，從而降低下一次查找的複雜度。運行時間68ms。

class Solution: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ n = len(nums) A = [[i, num] for i, num in enumerate(nums)] A = sorted(A, key=lambda x: x[1], reverse = True) A_min = target - A[0][1] A_max = target - A[n - 1][1] A = filter(lambda x: A_min <= x[1] <= A_max, A) idxs = [] numbers = [] for idx, number in A: idxs.append(idx) numbers.append(number) idx_left = None while 1: idx_right = idxs.pop() num_right = numbers.pop() num_left = target - num_right try: idx_left = idxs[numbers.index(num_left)] break except: pass return [idx_left, idx_right]

受討論區啟發後寫的代碼：

建立字典，遍曆數組，每個值的匹配值如果不在字典中就把這個值放入字典，直到找到匹配值為止。運行時間49ms。

class Solution: def twoSum(self, nums, target): dic = {} for idx, num in enumerate(nums): if target - num in dic: return [dic[target - num], idx] else: dic[num] = idx

推薦閱讀：