[LeetCode] Two Sum

题意

在数组 nums 中找到两个不重复的数字 nums[x] 和 nums[y],使 nums[x]+nums[y]=target。

输出 x 和 y。

数据保证有答案。

题解

应该不难吧。

方法一

我比较崇尚暴力…… 恩。

遍历,t = target - nums[i],如果 t 也在 nums 中并且 t 的序号不为 i,说明找到了一组解。

代码

结果

16 / 16 test cases passed.
Status: Accepted
Runtime: 848 ms

方法二

为什么方法一那么慢呢?因为 pos = nums.index(t) 这句话耗时比较长,整体程序复杂度为 O(n^2)

那么。如何把复杂度降下来呢?或者,pos = nums.index(t) 这句话,能不能有什么快速的办法?

字典。Python 的字典。

我们把出现过的数字的位置全部拿字典记录下来。这样就可以用 O(1) 的时间找出某个数字出现的位置。

代码

结果

16 / 16 test cases passed.
Status: Accepted
Runtime: 44 ms

桩程序

发表评论

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