1. Two Sum

本題是 Leetcode Top 100 liked questions 中的第一題。

1. Two Sum

Easy

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

題意

題意很好理解，給你一個數列，和一個目標值。請你從數列中找出兩個數，它們的和就是這個目標值，並返回這兩個數的索引。題目給出了一個限制，同一索引不能取用兩次，而且給出了一個假設，那就是列表中只有一組解。

分析

初拿到這個題目，便想到利用字典去取值，每拿到一個數i，把它存到字典里去，key就是target-i,而對應的value是i的索引值，這樣對後面每個數，我都會去看它是不是在字典當中，如果在，那麼就找到了解，直接返回索引即可，如果不在，那麼我們把它再如同之前一樣加到字典裡面去。如此，只需遍歷一遍數列就可以找到解了，複雜度為O(N)。但是也有缺點，它佔用了多餘的空間。時間與空間是演算法里矛盾的兩端。

還有另外一種思路，那就是每取到一個值i，就去列表裡去索引target-i如果找到就返回，找不到就繼續找，但是演算法複雜度是O(N^2)的，好處在於沒有用多餘的空間

Python 實現

#第一種思路 class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ d1=dict() for i,j in enumerate(nums): if j not in d1: d1[target-j]=i else: return [d1[j],i]#第二種思路 class Solution(object): def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ for i in nums: if target-i in nums[nums.index(i)+1:]: return [nums.index(i),nums[nums.index(i)+1:].index(target-i)+nums.index(i)+1]

Python Tips

• 字典查詢key的複雜度為O(1)
• enumerate函數的用法：

new built-in function, enumerate(), will make certain loops a bit clearer. enumerate(thing), where thing is either an iterator or a sequence, returns a iterator that will return (0, thing[0]), (1, thing[1]), (2, thing[2]), and so forth.

#A common idiom to change every element of a list looks like this:for i in range(len(L)): item = L[i]# ... compute some result based on item ... L[i] = result#This can be rewritten using enumerate() as:for i, item in enumerate(L):# ... compute some result based on item ... L[i] = result

推薦閱讀：