Leetcode 1.两数之和

Posted on |

1. 两数之和

题目

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

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

1
2
3
4
5
6
示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

方法

方法1：暴力求解

遍历每个元素x，并且遍历后续元素中是否等于target-x

  • 时间复杂度：$O(n^2)$，每个元素，都需要和数组中后面的元素做对比，花费时间O(n)，所以一共花费时间$O(n^2)$
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n=len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if nums[j]==target-nums[i]:
                    return [i,j]

方法2：一次遍历哈希表

同时遍历和插入元素到哈希表中，每遇到一个元素x，向前检查target-x是否已存在于哈希表中。如果存在就立刻返回，否则将其元素值-索引（key-valur）保存到哈希表中。

  • 时间复杂度：O(n)。遍历数组中每个元素1次。查找哈希表中的元素只需要花费时间O(1)
  • 空间复杂度：O(n)。需要额外的空间，这依赖于存储在哈希表中的元素个数，最多n个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n=len(nums)
        dic=dict()
        for i,n in enumerate(nums):
            if target-n in dic:
                return [dic[target-n],i]
            dic[n]=i