題目

Two Sum

分析

1. 數(shù)組沒說是有序的
2. 乍一看只有O(N^2)的算法。
3. 不能進(jìn)行排序，會(huì)破壞索引值。
4. 數(shù)組中的元素會(huì)重復(fù)（樣例中有[3,3]這個(gè)數(shù)據(jù)）

Python語法

1. 排序
   list.sort()會(huì)改變list本身
   sorted(list)不改變list本身，形成一個(gè)新的list
2. 同時(shí)獲取List的值與索引

list = [2, 7, 5, 9]
for index, item in enumerate(list):
    print(index, item)

3. List添加元素

• append()

a = [1,2,3]
b = [3,4,5]
a.append(b)
print(a)
# [1, 2, 3, [3, 4, 5]]

• extend()

a = [1,2,3]
b = [3,4,5]
# a.append(b)
a.extend(b)
print(a)
# [1, 2, 3, 3, 4, 5]

代碼

我的代碼

直接雙重循環(huán)，時(shí)間復(fù)雜度N^2

哈希表

• 思路
  已知一個(gè)值i，找到另一個(gè)值等于target-i的時(shí)間復(fù)雜度是O(n)?？梢越⒁粋€(gè)Hash表，將O(n)降低到O(1)?？梢栽诮跤诔?shù)時(shí)間內(nèi)找到所要的值（前提是沒有發(fā)生Hash碰撞，本題不會(huì)發(fā)生）。
• 缺點(diǎn)
  開辟了額外的存儲空間

def twoSum(nums, target):
    '''
    for index_i, i in enumerate(nums):
        # print(index_i, i)
        for index_j, j in enumerate(nums):
            if i + j == target and index_i != index_j:
                l = []
                l.append(index_i)
                l.append(index_j)
                return l
    '''
    dict = {}
    l = []
    for index, i in enumerate(nums):
        dict[i] = index
    for index,i in enumerate(nums):
        number = target - i
        if number in dict.keys() and dict[number] != index:
            l.append(index)
            l.append(dict[number])
            return l

L = [3,2,4,5,6,7,8]
print(twoSum(L, 6))