LeetCode 1 Two Sum

一、题目链接

https://leetcode.com/problems/two-sum/

二、解答

2.1 解法一，暴力求解

直接使用暴力求解方法。这个不需要思考，直接就可以写出来。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> 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.2 解法二，两次遍历

利用 Python 中的字典这一数据结构。其中，key 存的是 nums[i]，value 存的是 i，这里的 i 是给定数组的索引值。

代码如下

class Solution2:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i in range(0, len(nums)):
            dic[nums[i]] = i
        for i in range(0, len(nums)):
            complement = target - nums[i]
            if complement in dic.keys() and dic[complement] != i:
                return [i, dic[complement]]

这个解法采用了两次遍历的方法

• 第一次遍历时，如果 nums 列表中有重复的元素，那么最后 dic[nums[i]] 存储的值将是最后一次的 i；
• 第二个遍历中，if 语句要考虑两种情况
  • 一是最后的两个 two nums 的值是不同的，那么，很显然，dic[target - nums[i]] 就是与当前的 i 对应的另一个索引值；
  • 二是最后的两个 two nums 的值是重复的，而且，根据题目给定的条件，题目一定有解，且是唯一解，那么，当前的 i 一定是索引值较小的那一个，dic[target - nums[i]] 则是另一个。

时间复杂度：$O(N)$ 空间复杂度：$O(N)$

2.3 解法三，一次遍历

思想和解法二基本是一样的。

class Solution3:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i in range(0, len(nums)):
            complement = target - nums[i]
            if complement in dic.keys():
                return [dic[complement], i]
            dic[nums[i]] = i

我们只需要理解一点，找到相应的解时，分两种情况

• 一，最后的两个 two nums 的值是不同的，那么，i 的值是大于 dic[target - nums[i]] 的；
• 二，最后的两个 two nums 的值是重复的，那么，i 的值还是大于 dic[target - nums[i]] 的，和第一种情况没什么不同，之所以分两种情况，是为了捋得更清楚一些。

时间复杂度：$O(N)$ 空间复杂度：$O(N)$

三、完整代码

# -*- coding: utf-8 -*-
# @File  : leet_01.py
# @Author: FanLu
# @Date  : 2021/7/9

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> 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]

class Solution2:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i in range(0, len(nums)):
            dic[nums[i]] = i
        for i in range(0, len(nums)):
            complement = target - nums[i]
            if complement in dic.keys() and dic[complement] != i:
                return [i, dic[complement]]
        return [] # 不存在的情况

class Solution3:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i in range(0, len(nums)):
            complement = target - nums[i]
            if complement in dic.keys():
                return [dic[complement], i]
            dic[nums[i]] = i

if __name__ == '__main__':
    solution = Solution()
    nums = [3, 2, 4]
    target = 6
    res = solution.twoSum(nums, target)
    print(res)