LeetCode-1

概述

作为简单题的第一题(Two Sum),简答来说就是给出一个序列以及目标值,求出能加和出目标值的两个数字在数组中的下标。

分析

这个题目可以说是一目了然,直接能够想到的解法就是遍历这一个序列,然后遍历下标大于当前遍历到的数字的元素,如果有匹配的数字就直接返回结果即可。

如果单纯遍历,时间复杂度高达O(n2),这个复杂度不太令人满意。

那么是否可以通过空间换时间呢?自然是没问题的。

后续考虑通过使用HashMap的方式记录每个值对应的元素的下标,每次检查是否有当前值相加得到目标值的的key存在,将时间复杂度降低到了O(n),不过空间复杂度也上升到了O(n)

解法

发表评论

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

*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">