Leetcode笔记

最近开始刷leetcode,在这里记录一下做题的过程,不定期更新。

GitHub:https://github.com/nyanim/leetcode

Two Sum(Easy)

https://leetcode.com/problems/two-sum/

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.

解法1:暴力搜索

题目本身很简单,使用两个for循环遍历即可。需要注意的是同一元素不能使用两次,因此在遍历时,内层循环需要直接从外层循环+1处开始,而不是从头开始。

Solution:https://github.com/nyanim/leetcode/blob/master/TwoSum.py

解法2:哈希表

新建一个哈希表(Python中使用字典即可),遍历数组,以数组中的值为哈希表的键,以数组中的键为哈希表的值,将数组中的内容存入哈希表。

在遍历的同时检查(target-当前遍历到的值)是否存在哈希表的键中,如果存在则返回哈希表中的值和当前遍历到的键。这样复杂度由O(n^2)降低至O(n)。

Solution:https://github.com/nyanim/leetcode/blob/master/TwoSum(Hashmap).py