欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[LeetCode] 1. Two Sum 两数之和

程序员文章站 2022-04-16 08:37:25
Part 1. 题目描述 (easy) Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each ......

part 1. 题目描述 (easy)

given an array of integers, return indices of the two numbers such that they add up to a specific target.

you may assume that each input would have exactly one solution, and you may not use the same element twice.

example

given nums = [2, 7, 11, 15], target = 9, because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

part 2. 分析

 本题是leetcode的第一题,求解题目并不难,但是如何进一步优化时间复杂度是本题的重点。需要用到的基础是hash table,在python中可以用字典来实现。

part 3. 解决方案

【方法1: 暴力求解 (brute force)】

 最简单直接的求解方式,遍历所有两个数的组合,将两数之和跟target的值进行比较。时间复杂度o(n2),空间复杂度o(1)。

 python 代码如下:

1 class solution:
2     def twosum(self, nums, target):
3         for i in range(len(nums)):
4             for j in range(i+1, len(nums)):
5                 if nums[i] + nums[j] == target:
6                     return [i, j]

【方法2: one-pass hash table】

如果我们想要降低时间复杂度,该如何解决呢?我们可以借助hash函数来实现,因为它可以免除了第二轮的遍历过程,使搜索时间变为o(1),总的时间复杂度降低为o(n)。但相应的,其空间复杂度会变复杂,变为o(n)。

python 代码如下:

1 class solution:
2     def twosum(self, nums, target):
3         dict_nums = {}   # key: num  values: index
4         for i in range(len(nums)):
5             rest = target - nums[i]
6             if rest in dict_nums:
7                 return [dict_nums[rest], i]
8             dict_nums[nums[i]] = i

备注:注意判断hash中是否存在需要的数字(line 5-7)和添加新数字到hash中(line 8)的顺序,如果反过来写,某些case会出错,比如nums = [3,3,1,4], target = 6. 因为在hash中,我们将数字作为key来存储,这要求key是唯一的。如果我们先执行存储操作的话,当出现2个相同数字的时候就会报错。

part 4. 心得体会 

       刚开始接触leetcode,想通过刷算法题的方法把算法、数据结构的基础知识好好巩固一番。因为主要不是为了面试而刷题,所以做题顺序上可以更随心所欲一些。准备先做top 100的题目,然后其余的题目顺序待定。编程语言准备以python为主,虽然java、c++都用过,但是都没有到熟练掌握的程度。因为以后可能更多的会用python来做实验,所以正好这回多写点python程序,提升代码水平,希望自己能坚持下去咯!

       完事开头难,这一题虽然是easy级别的,但是自己在第一次写暴力求解代码的时候还是粗心出了错,脑子有点跟不上节奏啊......在学习方法2的时候,因为对python字典不怎么了解,还花时间去学习了字典的基本操作。再加上这是我第一次在博客上写技术的东西(以前都是私底下用有道笔记),所以花了不少时间,但是已经从中感受到乐趣啦。