呦呵丶晓晓的博客


一只贪吃嗜睡的呆萌程序员

LeetCode题解 - 01.两数之和

  • 1057 字
  • 次阅读
  • 条评论
  1. 1. 题目
  2. 2. 题解
    1. 2.1. 暴力法
    2. 2.2. 哈希表

题目

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]

题解

暴力法

确定第一个元素i，然后搜索其后的元素j，当满足条件nums[i] + nums[j] == target时，返回[i,j]

  • 时间复杂度：O(n^2^)
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        for i in range(length):
            for j in range(i + 1, length):
                if nums[i] + nums[j] == target:
                    return [i, j]

哈希表

将元素放入HashMap中，使用元素值作为Key，元素的索引作为Value
查找时当使用target - num[i]为Key的元素存在则返回[HashMap[target - num[i]],num[i]]

  • 时间复杂度 O(n)
  • 空间复杂度 O(n)

使用测试样例测试返回值为[1,0],与给定结果的[0,1]顺序不符，但也能通过。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        table = dict()
        for i in range(len(nums)):
            n = nums[i]
            tmp = target - n
            if tmp in table:
                return [i, table[tmp]]
            else:
                table[n] = i
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
分享这一刻
让朋友们也来瞅瞅！