【Leetcode】题解[email protected] --Two Sum

题目来源：

https://leetcode.com/problems/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.

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

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

题意分析：

      这道题目是输入一个数组和target，要在一个数组中找到两个数字，其和为target，从小到大输出数组中两个数字的位置。题目中假设有且仅有一个答案。

题目思路：

1.暴力解法：

用 i 遍历 nums 中的每一个元素, 然后看该元素与后面的元素之和是否等于 target.

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

复杂度分析:

• 时间复杂度: O(n^2)
• 空间复杂度: O(1)

2.两遍哈希表

哈希表的构建和查找是分开进行的，先遍历一遍 nums, 构建哈希表(元素的值作为 key, 元素的位置作为 value, 这样就可以通过哈希表来确定元素在 nums 中的位置), 然后再次遍历 nums, 通过该哈希表确定是否有元素等于 target - nums[i]

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashdict = { num: index for index, num in enumerate(nums)}
        for i, num in enumerate(nums):
            sub= target - num
            if sub in hashdict and i != hashdict[sub]:
                return [i, hashdict[sub]]

复杂度分析:

• 时间复杂度: O(n)
  由于用了哈希表, 所以查找时间变成了O(1), 总时间复杂度O(n + (n + 1)) = O(n)
• 空间复杂度: O(n)
  哈希表里存放 n 个元素

3.一遍哈希表

边构建哈希表边查找, 相比第2种方法进一步降低运行时间

class solution(object):
    def sum(self,nums,target):
        dict ={}
        for i,num in enumerate(nums):
            sub = target - num
            if sub in dict and i!= dict[sub]:
                return[dict[sub],i]
            dict[num] = i
        
if __name__ == '__main__':
    nums = [2,7,11,15]
    s = solution()
    sum=s.sum(nums,9)
    print(sum)