【記錄帖】（No.001）從零打卡刷Leetcode

08-22

10 人贊了文章

寫在前邊：

小詹一直覺得自己編程能力不強，想在網上刷題，又怕不能堅持。不知道有木有和小夥伴和小詹一樣想找個人一起刷題呢？歡迎和小詹一起定期刷leetcode，每周一周五更新一題，每一題都吃透，歡迎一題多解，尋找最優解！歡迎小夥伴們把自己的思路在留言區分享出來噢~

No.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.

題目大意：給出一個數字列表和一個目標值（target），假設列表中有且僅有兩個數相加等於目標值，我們要做的就是找到這兩個數，並返回他們的索引值。

例如：

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

小詹第一反應就是兩層循環就可以解決，小case，的確思路簡單，但是時間複雜度，你懂得！很簡單就能想到的代碼如下：

def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ result = [] for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[i] + nums[j] == target: result.append(i) result.append(j) return result

其實這裡也可以用一層循環即可實現，因為我們知道有且僅有一個解；我們可以通過判斷target與某一個元素的差值是否也在列表之中即可，這個和兩層循環思路類似，但是不難想到計算次數就下降了，代碼如下：

def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ result = [] for i in range(len(nums)): oneNum = nums[i] twoNum = target - oneNum if twoNum in nums: j = nums.index(twoNum) if i != j: result.append(i) result.append(j) return result

的確兩種方案都輕鬆通過了，but用時過長，排名老靠後了。之後小詹在網上找到了另一種方案，整體思路和一層循環的方案二有點類似：通過創建字典，將nums里的值和序號對應起來，並創建另一個字典存儲目標值（Target）-nums的值，通過判斷該值是否在nums內進行判斷並返回其對應索引值，代碼如下：

def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ # 創建字典一，存儲輸入列表的元素值和對應索引 num_dict = {nums[i]:i for i in range(len(nums))} print(num_dict) # 創建另一個字典，存儲target-列表中的元素的值，小詹稱為num_r吧，好表達 num_dict2 = {i:target-nums[i] for i in range(len(nums))} print(num_dict2) # 判斷num_r是否是輸入列表中的元素，如果是返回索引值，不是則往下進行 result = [] for i in range(len(nums)): j = num_dict.get(num_dict2.get(i)) if (j is not None) and (j!=i): result = [i,j] break return result

該方案，在時間效率上還較為理想，小詹親測結果排名如下：

不知道小夥伴們能否提出更加節約時間的方案呢？如果有請聯繫小詹，在下一次打卡時候分享給大家！獨樂樂不如眾樂樂噢！

往期推薦：

1. 深度學習入門筆記系列 ( 三 )

2. 深度學習入門筆記系列 ( 二 )

3. 深度學習入門筆記系列 ( 一 )

歡迎您的轉發分享

http://weixin.qq.com/r/5ihKUkjEdxUIrQwx9330 (二維碼自動識別)

▲長按關注我們