题目描述

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

注意

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例1

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例2

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例3

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

方法一：暴力双循环

复杂度

时间复杂度为：O(n^2)

思路

1、定义两个指针，分别代表第一个数的索引first_index和第二个数的索引second_index

2、双层循环遍历，判断两个索引所指数字之和是否等于target，若等于则返回两个索引。

提示

因题目中要求同一元素不能在答案中重复出现，所以第二个索引应该从第一个索引后的元素开始遍历

代码

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

if __name__=='__main__':
    solution = Solution()
    print(solution.twoSum([2,7,11,15],9))
    print(solution.twoSum([3,2,4],6))
    print(solution.twoSum([3,3],6))

方法二：哈希法

复杂度

时间复杂度为：O(n)

思路

1、利用字典模拟哈希，创建一个空字典，通过enumerate方法将列表中的元素存入字典中，注意要将值存为key，索引存为value。

2、通过for循环enumerate(nums)，获取到第一个数，然后根据target-value获取第二个值，然后判断该值是否在上一步中的字典中存在，若存在则返回第二个值得索引，即该值在字典中的value。

更优写法

取消第一步中提前将数据存入字典的做法。先定义一个空字典，然后在第二步中一边遍历一边往字典中插入数据

代码

先创建完整字典，再做循环查找

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        record = dict()
        for index,value in enumerate(nums):
            record[value]=index
        for index,value in enumerate(nums):
            if target-value in record and record[target-value]!=index:
                return [index,record[target-value]]


if __name__=='__main__':
    solution = Solution()
    print(solution.twoSum([2,7,11,15],9))
    print(solution.twoSum([3,2,4],6))
    print(solution.twoSum([3,3],6))

一边循环一边向字典中插入数据，更优

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        record = dict()
        for index,value in enumerate(nums):
            if target-value in record and record[target-value]!=index:
                return [index,record[target-value]]
            else:
                record[value]=index


if __name__=='__main__':
    solution = Solution()
    print(solution.twoSum([2,7,11,15],9))
    print(solution.twoSum([3,2,4],6))
    print(solution.twoSum([3,3],6))