[LeetCode] 1. Two Sum 两数之和

汪星人 2018-10-12 01:4560 阅读

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字典不怎么了解,还花时间去学习了字典的基本操作。再加上这是我第一次在博客上写技术的东西(以前都是私底下用有道笔记),所以花了不少时间,但是已经从中感受到乐趣啦。

 

回复数量: 0
暂无评论~~
  请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!