美文网首页我爱编程
Leetcode Python超琐碎笔记: 001. Two S

Leetcode Python超琐碎笔记: 001. Two S

作者: simoncos | 来源:发表于2018-04-16 23:20 被阅读750次

    超琐碎 ≈ 完整记录 + 深入探究 + 任性吐槽

    问题地址,难度:Easy,标签:Array | Hash Table

    若有错误之处请予以指正:)

    问题描述

    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.

    Example:

    Given nums = [2, 7, 11, 15], target = 9,
    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].

    题意分析

    • 同一个数最多用一次:Given nums = [1], target = 2 -> return [0, 0] 错误输出
    • 列表中可能含负整数:Given nums = [-3, -1, 11, 3], target = -4 -> return [0, 1]
    • 列表中可能有相等数字:Given nums = [3, 7, 11, 3], target = 6 -> return [0, 3]
    • 唯一解:不会出现这样一些case:
      • Given nums = [3, 1, 11, x, x, x, ..., x, 3], target = 4
      • Given nums = [3, 2, x, x, x, ..., x, 1, 4], target = 5
    • 返回顺序无限制:Given nums = [2, 7, 11, 15], target = 9 -> return [1, 0] or [0, 1]

    我的实现及调优过程

    方法1:3460 ms
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            i = 0
            while(i<len(nums)-1):
                a = nums[i]
                for b in nums[i+1:]:
                    if target - a == b:
                        return [i, nums[i+1:].index(b)+i+1]
                i += 1
    

    暴力解法,两层循环。

    • 时间复杂度:O(n^2)
    • 空间复杂度:O(1)
    方法2:3189 ms
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            i = 0
            while(i<len(nums)-1):
                a = nums[i]
                nums_ = nums[i+1:]
                for b in nums_:
                    if target - a == b:
                        return [i, nums_.index(b)+i+1]
                i += 1
    

    小改动,减少了切片的冗余使用。

    • 时间复杂度:O(n^2)
    • 空间复杂度:O(1)
    方法3:1197 ms
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            i = 0
            while(i<len(nums)-1):
                a = nums[i]
                nums_ = nums[i+1:]
                if target - a not in nums_:
                    i += 1
                    continue
                for b in nums_:
                    if target - a == b:
                        return [i, nums_.index(b)+i+1]
    

    在第一层循环中,首先使用in检查(target-a)这个值是否在剩下的数组nums_里,如果在,才进入下一层循环从nums_找到(target-a)值的位置,省了逐个进行target - a == b的计算时间。

    • 时间复杂度:O(n^2)
    • 空间复杂度:O(1)
    方法4:1228 ms
    from collections import defaultdict
    
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            
            value2index = defaultdict(list)
            for i, e in enumerate(nums):
                value2index[e].append(i)
    
            i = 0
            while(i < len(nums)-1):
                a = nums[i]
                nums_ = nums[i+1:]
                if target - a not in nums_:
                    i += 1
                    continue
                for b_index in value2index[target-a]:
                    if b_index != i:
                        return [i, b_index]
    

    使用defaultdict(list)命名为value2index,首先循环遍历列表nums,将每个数的值与其位置记录在value2index中,值作为key,位置放入value(list);接下来再循环一遍列表nums,找出target-a的值并在value2index里查出其在nums的位置,如果位置与a不同,输出;否则继续。省了逐个进行target - a == b的计算时间。

    • 时间复杂度:O(2n) ~ O(n) (虽然有两层循环,但第二层有唯一解作为bound)
    • 空间复杂度:O(n)
    方法5:44 ms
    from collections import defaultdict
    
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            value2index = defaultdict(list)
            for a_index, a in enumerate(nums):
                value2index[a].append(a_index)
                for b_index in value2index[target-a]:
                    if b_index != a_index:
                        return [a_index, b_index]
    

    这一次有飞跃式的进步,仍然使用defaultdict(list)作为value2index,但是value2index中每次加入nums里的值a后,紧跟着去查value2index有没有成功与该值配对的target-a值,这样nums只会被循环遍历一次。

    • 时间复杂度O(n)
    • 空间复杂度O(n)
    方法6:38 ms
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            """
            value2index = dict()
            for a_index, a in enumerate(nums):
                b_index = value2index.get(target-a, None)
                if b_index not in (None, a_index):
                    return [a_index, b_index]
                value2index[a] = a_index
    

    细想之下,之前之所以用defaultdict(list),而不是dict作为value2index,是担心nums中如果有相同的值a1和a2时,在a2加入value2index时a1会被覆盖掉,但是这会不会影响算法的正确性呢?考虑下面几种特殊情况,似乎并不会有问题:

    • a等于target-a
      • Given nums = [3, 1, 2, 3], target = 6只要第二个3在加入dict前做查询,第一个3就不会被覆盖,OK)
      • Given nums = [3, 1, 2, 3, 3], target = 6 (由于唯一解的限制,这种情况不存在)
      • Given nums = [3, 1, 2, 2, 3], target = 62被覆盖,但无所谓,OK)
      • Given nums = [3, 1, 2, 4], target = 62被覆盖,但无所谓,OK)
    • a不等于target-a
      • Given nums = [3, 4, 2, 1], target = 4(OK)
      • Given nums = [2, 2, 3, 4], target = 5(唯一解限制,情况不存在)
    • 两组解,一组a等于target-a,一组a不等于target-a(唯一解限制,情况不存在)
      • Given nums = [3, 1, 2, 4], target = 6

    方法6等同于Leetcode网站上的Solutions(JAVA)里提到的最优方法,不过这种方法固然是快,但思路不够自然,要考虑一堆犄角旮旯的case,现实里测试总是难保证覆盖全所有情况。从实践角度上来讲,使用的假设强度和性能需要有个平衡,因此我觉得方法5相对更好。

    • 时间复杂度O(n)
    • 空间复杂度O(n)

    相关文章

      网友评论

        本文标题:Leetcode Python超琐碎笔记: 001. Two S

        本文链接:https://www.haomeiwen.com/subject/ablykftx.html