leetcode 1. 兩數(shù)之和題目：

給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個(gè)數(shù)。

你可以假設(shè)每個(gè)輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

第一種解決方法（暴力解決）:

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """

    for i, v in enumerate(nums):

        for l, k in enumerate(nums):
            if i == l:
                continue
            if k + v == target:
                return [i,l]

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n^2)O(n 2 )， 對于每個(gè)元素，我們試圖通過遍歷數(shù)組的其余部分來尋找它所對應(yīng)的目標(biāo)元素，這將耗費(fèi) O(n)O(n) 的時(shí)間。因此時(shí)間復(fù)雜度為 O(n^2)O(n 2 )。

空間復(fù)雜度：O(1)O(1)。

第二種方法（hash值）：

利用list的index() 和collections中defaultdict

def twoSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[int]
    """
    from collections import defaultdict
    d = defaultdict(list)
    [d[v].append(i) for i, v in enumerate(nums)]

    for i, v in enumerate(nums):
        second_value = target - v
        try:
            index_li = d[second_value]
            for l in index_li:
                if i == l:
                    continue
                return [i, l]
        except KeyError:
            continue    

復(fù)雜度分析：

時(shí)間復(fù)雜度：O(n)O(n)， 我們只遍歷了包含有 nn 個(gè)元素的列表一次。在表中進(jìn)行的每次查找只花費(fèi) O(1)O(1) 的時(shí)間。

空間復(fù)雜度：O(n)O(n)， 所需的額外空間取決于哈希表中存儲的元素?cái)?shù)量，該表最多需要存儲 nn 個(gè)元素。
原文網(wǎng)址：http://www.chenxm.cc/post/710.html