力扣题（1）—— 两数之和

两数之和

题目内容

给定一个整数数组 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(n2) 的算法吗？

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/two-sum

题解

题解一：双循环暴力解法

看到这个题目的第一反应就是双循环解法。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        for i in range(0, length):
            for j in range(i+1, length): # 因为一定有答案，不用考虑第二层循环的边界问题，即 i+1 一定不会等于 length
                if nums[i] + nums[j] == target:
                    return [i, j]

很显然，因为是双循环暴力解法，所以在力扣上通过的时间比较长，大概是 3344 ms

题解二：双循环解法进阶版

第一种题解的双循环是无脑的双循环，根本不判断是否有必要双循环——比如说是否有数字和第一层循环的数字相加等于我们的目标数字。
所以在进阶版中我们需要做的就是在进行第二层循环前加一层判断判断是否有必要进行第二层循环。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        for i in range(0, length):
            if (target - nums[i]) in nums: # 判断是否有必要进行第二层循环
                for j in range(i+1, length):
                    if nums[j] + nums[i] == target:
                        return [i, j]

力扣通过的时间大约是728 ms

题解三：利用 python 函数 index

不进行双循环直接查找 target - nums[i]数字在列表中的位置

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(0, len(nums)):
            num1 = target - nums[i]
            if num1 in nums: # 判断 target - nums[i] 是否在列表中
                j = nums.index(num1)
                if j != i: # 判断定位到的数字位置是否和第一次循环数字位置一致
                    return [i, j]

力扣通过的时间大约是724 ms

题解四：字典模拟哈希表

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {
    } # 字典 key 值记录数字，value 记录下标，因为只有一个答案，不用考虑数字相同的情况而造成的覆盖导致答案不全的问题

        for i in range(0, len(nums)):
            num1 = target - nums[i]
            if num1 in dic: # 判断数字是否存在于 字典中
                return [dic.get(num1), i]
            dic[nums[i]] = i # 记录数字和下标

力扣通过的时间大约是40 ms