六、问题:2-sum问题


返回

两数之和问题:给定一个列表和一个整数,从列表中找到两个数,使得两数之和等于给定的数,返回两个数的下标。题目保证有且只有一组解

6.1 方法一

  • 遍历列表,逐个取元素n1,同时再逐个取n1右侧数n2,判断 n1 + n2 是否满足条件,满足条件时直接返回两者下标
def two_sum_1(nums, target):
    """
    时间复杂度:O(n*n)
    :param nums:
    :param target:
    :return:
    """
    n = len(nums)
    for i in range(n - 1):
        n1 = nums[i]
        for j in range(i + 1, n):
            n2 = nums[j]
            if n1 + n2 == target:
                return i, j
              

6.2 方法二:

  • 遍历列表,逐个取元素n1,计算出另一个数 n2 = target - n1,判断n2是否在列表内
def two_sum_2(nums, target):
    """
    时间复杂度:O(n*k),k为python查找某个元素是否在列表内的时间复杂度
    :param nums:
    :param target:
    :return:
    """
    for n1 in nums:
        n2 = target - n1
        if n2 in nums:  # 判断n2是否在列表内
            if n1 != n2:
                return nums.index(n1), nums.index(n2)
            else:  # n1和n2重复
                return nums.index(n1), nums.index(n2, nums.index(n1) + 1)
              

6.3 方法三

  • 在方法2的基础上,将列表排序,以用二分法判断n2是否在列表内,提高查找效率
def search(li, val):
    """
    二分查找方法
    :param li:
    :param val:
    :return:
    """
    left = 0
    right = len(li) - 1
    while left <= right:
        mid = (left + right) // 2
        if val == li[mid][0]:
            return mid
        elif val > li[mid][0]:
            left = mid + 1
        elif val < li[mid][0]:
            right = mid - 1
    else:
        return -1


@cal_time
def two_sum_3(nums, target):
    """
    时间复杂度:O(n*logn)
    :param nums:
    :param target:
    :return:
    """
    nums_ = [[num, index] for index, num in enumerate(nums)]
    nums_.sort(key=lambda x: x[0])  # 按值排序
    for i in range(len(nums_)):
        n1 = nums_[i][0]
        n2 = target - n1
        j = search(nums_, n2)  # 二分法判断n2是否在列表内
        if j >= 0:
            if n1 != n2:
                return nums_[i][1], nums_[j][1]
            else:  # n1和n2重复
                return nums.index(n1), nums.index(n2, nums.index(n1) + 1)
              
返回