LeetCode第1题:Two Sum总结

万事开头难,算是开始刷leetcode了吧,不知道能不能坚持下去!在这放下一句,不坚持是小狗!——jc,15.10.25

第一题能就是一个纯属熟悉环境,从网上找了python版答案走了一遍流程:

题目

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

python

然后看到了题解:

O( n^2 ) runtime, O(1) space – Brute force:

The brute force approach is simple. Loop through each element x and find if there is another value that equals to target – x. As finding another value requires looping through the rest of array, its runtime complexity is O( n^2 ).

O(n) runtime, O(n) space – Hash table:

We could reduce the runtime complexity of looking up a value to O(1) using a hash map that maps a value to its index.

题解大意就是用直接遍历(暴力破解)的话就是O( n^2 ),但是用哈希表就是O(n)的复杂度。具体到python语言就可以使用内置的字典(dict)直接编写了。

后来看了看C++的题解,尝试写了一个C++版本的代码:

C++(数组)

C++(STL map)

Java

(题解答案,暂时不会java)


  • 参考:

[1] http://blog.csdn.net/hcbbt/article/details/43966403 [LeetCode] 001. Two Sum (Medium) (C++/Java/Python)

发表评论

电子邮件地址不会被公开。 必填项已用*标注