LeetCode：1.两数之和 Python | list.index()、哈希表

leetcode在线答题网址：https://leetcode-cn.com/problems/
解题思路参考：CSDN：coordinate_blog 讲的真不错
题目：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

#方法一：暴力法，两个for循环
#coding:utf-8
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        l = []
        nums_len = len(nums)
        for i in range(nums_len):
            for j in range(i+1, nums_len):
                if nums[i]+nums[j]==target:
                    return [i, j]

#方法二：暴力法，但是减小时间复杂度
#list.index()查找元素对应的下标
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        nums_len = len(nums)
        for i in range(nums_len):
            temp = target - nums[i]
            if temp in nums[i+1:]:
                temp_key = nums[i+1:].index(temp) + i+1 #找到temp所对应的的下标，但是防止nums里面含有相同的元素，所以按照上面的顺序从i+1处开始计算temp的下标，然后再加上i+1
                return [i, temp_key]

#方法三：
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        nums_len = len(nums)
        for i in range(nums_len):
            temp = target - nums[i]
            if temp in nums[:i]: #不从i后面搜索了，从i之前搜索，缩小搜索范围;i作为第二个输出元素
                return [nums.index(temp), i]



#方法四：哈希表
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        nums_hash = {}
        for i in range(len(nums)):
            temp = target - nums[i]
            if temp in nums_hash: #同方法三，但是这里用哈希表来存储nums[:i]，省去了搜索的步骤
                return [nums_hash[temp], i]
            else:
                nums_hash[nums[i]] = i