[LeetCode] 1. Two Sum 两数之和
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字典不怎么了解,还花时间去学习了字典的基本操作。再加上这是我第一次在博客上写技术的东西(以前都是私底下用有道笔记),所以花了不少时间,但是已经从中感受到乐趣啦。
上一篇: python中文件操作的基本方法
下一篇: php无限极分类递归排序实现方法