站点图标 Wankko Ree's Blog

[刷题]LeetCode 1. 两数之和

代码git:History for 1. 两数之和.py - WankkoRee/LeetCodeAnswersWithPython3

为了明年的就业面试,所以准备刷题了,而力扣是出了名的笔试黄埔军校,所以就来刷力扣的题了。

从第一题来看,力扣对于各种边角条件的数据准备得还挺充分的,而且还能查看时空排名,整挺好。

刚开始看到这题,第一思路是遍历一次数据,然后每次算出另一个数是多少,判断下这个数是不是在数据里,在的话就返回俩数下标。(两重for的O(n ^ 2)压根没考虑)

所以就写出了这么个玩意。

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            y = target - x
            if y in nums:
                return [i, nums.index(y)]

solution = Solution()
print(solution.twoSum([2,7,11,15], 9))

然后就理所当然地err了,因为没考虑自身就是另一半的情况,具体数据是solution.twoSum([3,2,4], 6),于是就写了个数据相等就跳过的额外判断。

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            y = target - x
            if y == x:
                continue
            if y in nums:
                return [i, nums.index(y)]

solution = Solution()
print(solution.twoSum([2,7,11,15], 9))
print(solution.twoSum([3,2,4], 6))

然后还是理所当然地err,因为题目来了个solution.twoSum([3,3], 6),结果我的代码压根不返回东西了,因为按我的代码逻辑,这种重复出现的情况压根就没考虑过,于是那就推翻刚才的额外判断,直接改改另一个数的可查范围呗,然后就被数据给误导了写出个去掉首位的憨批代码。

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            y = target - x
            if y in nums[1:]:
                return [i, nums[1:].index(y) + 1]

solution = Solution()
print(solution.twoSum([2,7,11,15], 9))
print(solution.twoSum([3,2,4], 6))
print(solution.twoSum([3,3], 6))

所以这个代码肯定没过,卡的数据是solution.twoSum([2,5,5,11], 10),得把数据裁剪成当前位之后的半段数据才行,于是接着冲。

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            y = target - x
            if y in nums[i + 1:]:
                return [i, nums[i + 1:].index(y) + 1]

solution = Solution()
print(solution.twoSum([2,7,11,15], 9))
print(solution.twoSum([3,2,4], 6))
print(solution.twoSum([3,3], 6))
print(solution.twoSum([2,5,5,11], 10))

这个代码我本地测都没测就冲了,因为感觉没啥边缘情况没考虑到了,必拿下!结果就在历史数据翻车了,solution.twoSum([3,2,4], 6)都没过,本地看了下原来是另一个数的下标我只+1,而不是+i+1,我的锅。

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            y = target - x
            if y in nums[i + 1:]:
                return [i, nums[i + 1:].index(y) + i + 1]

solution = Solution()
print(solution.twoSum([2,7,11,15], 9))
print(solution.twoSum([3,2,4], 6))
print(solution.twoSum([3,3], 6))
print(solution.twoSum([2,5,5,11], 10))

终于过了所有数据,这第一题数据就这么离谱,有点期待后面的了。

执行用时: 468 ms , 在所有 Python3 提交中击败了 43.32% 的用户
内存消耗: 15.1 MB , 在所有 Python3 提交中击败了 85.64% 的用户
通过测试用例: 55 / 55


一觉睡醒尝试用空间换时间,把需要重复使用的值都给赋变量,然后时间确实小了一点,但是内存也大了一点。

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            y = target - x
            p = nums[i + 1:]
            if y in p:
                return [i, p.index(y) + i + 1]

solution = Solution()
assert solution.twoSum([2,7,11,15], 9) == [0, 1]
assert solution.twoSum([3,2,4], 6) == [1, 2]
assert solution.twoSum([3,3], 6) == [0, 1]
assert solution.twoSum([2,5,5,11], 10) == [1, 2]

执行用时: 376 ms , 在所有 Python3 提交中击败了 46.37% 的用户
内存消耗: 15.2 MB , 在所有 Python3 提交中击败了 75.08% 的用户
通过测试用例: 55 / 55

所以说应该是我这个思路差不多到极限了,那些同语言的其他人应该是另外的思路去解的(总不会有人搞针对数据的憨批输出脚本吧)。

于是打算将空间换时间进行到底,把数据的值和下标开个dict映射起来,然后原本数据的话因为不用管重复的情况了(已经可以在映射里表示出来了),所以就直接优化成set(in查找时set会比list快很多),然后再遍历的时候考虑下重复等特殊情况,大概思路就完事了,结果直接几乎重构了整个代码。

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_ = {}
        for i, d in enumerate(nums):
            if d not in nums_.keys():
                nums_[d] = [i]
            else:
                nums_[d].append(i)
        nums = set(nums)
        for x in nums:
            y = target - x
            if y in nums and (x != y or len(nums_[y]) >= 2):
                return [nums_[x][0], nums_[y][-1]]

solution = Solution()
assert solution.twoSum([2,7,11,15], 9) == [0, 1]
assert solution.twoSum([3,2,4], 6) == [1, 2]
assert solution.twoSum([3,3], 6) == [0, 1]
assert solution.twoSum([2,5,5,11], 10) == [1, 2]

执行用时: 40 ms , 在所有 Python3 提交中击败了 62.76% 的用户
内存消耗: 17.1 MB , 在所有 Python3 提交中击败了 5.09% 的用户
通过测试用例:55 / 55


The End
退出移动版