pythontip 100days-day7

Code › python
, ,

题目

输入一个listl和一个整数n,判断l中是否有两个元素的和等于n

例子

  • None输入 -> False
  • [],3 -> False
  • [1,3,5],4 -> True
  • [2,3,4,6],11 -> Flase

假设

  • list中元素均为整数

tips

  1. 利用两重循环搜索
  2. 记录已出现过的值

答案

解法1:

def two_sum(l, n):
    if l is None or n is None:
        return False
    for i in range(len(l)):
        for j in range(i + 1,len(l)):
            if l[i] + l[j] == n:
                return True
    return False

性能：

  1. 时间复杂度O(n^2)
  2. 空间复杂度O(1)

关键点：1.两重循环搜索

解法2:

def two_sum(l, n):
    if l is None or n is None:
        return False
    memo = {}
    for x in l:
        need = n - x
        if memo.get(need):
            return True
        memo[x] = True
    return False

性能：

  1. 时间复杂度O(n)
  2. 空间复杂度O(n)

关键点:

  1. 利用dict记录出现过的数字，后续直接查找dict即可

解法3：

def two_sum(l, n):
    if l is None or n is None:
        return False

    for x in l:  # O(n)
        """
            1. 遍历l，判断n-x是否在l中
            2. 如果n-x的差不等于x，那么l中存在两数之和等于n
            3. 如果n-x的差等于x，那么l中至少存在两个x才能保证l中存在两数之和等于n
        """
        if (n - x) in l and ((n != 2 * x) or (n == 2 * x and l.count(x) > 1)):
            return True

    return False

性能：

  1. 时间复杂度O(n^2)
  2. 空间复杂度O(n)

关键点:

  1. 判断n-x的差是否存在l中，如果n=2x，则判断l中x的数量应该大于等于2