Two Sum

Two Sum

描述

给定一个数组与一个数字, 从数组中找到两个数, 他们的和等于给定的数字, 输出这两个数的下标, 可以认为有且仅有唯一的解

示例:
输入: [3, 2, 5], 8
输出: [0, 2]

分析:

给定的数组是无序的, 要找到所有两个数字和的可能, 需要遍历所有组合, 复杂度是\(O(n^2)\) , 解如下:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

在这道题似乎并没有做超时限制, 这种解法已经可以通过了

如果给定的数组是有序的, 只需要做一次查找就能找到, 所以我们可以先排序再查找, 复杂度变为\(O(nlgn)\)

\(O(nlgn)\) 复杂度的排序有快速排序, 归并排序, 堆排序, 由于题目假定存在且只存在一个确定的解, 算法是否稳定并不重要, 我们可以使用快速作为例子, 按照基数的选择和分裂点选择的不同, 可以有好几种不同的写法

# use start flag as the base number
def _partation_sort1(l, start, end):
    flag = l[start]
    i = start
    for j in range(start + 1, end + 1):
        if l[j] <= flag:
            i += 1
        l[i], l[j] = l[j], l[i]
    l[i], l[start] = l[start], l[i]
    return i

# use end flag as the base number
def _partation_sort2(l, start, end):
    flag = l[end]
    i = start - 1
    for j in range(start, end):
        if l[j] <= flag:
            i += 1
        l[i], l[j] = l[j], l[i]
    l[i + 1], l[end] = l[end], l[i + 1]
    return i + 1

# use random flag as the base number
def _partation_sort3(l, start, end):
    r = random.randint(start, end)
    flag = l[r]
    i = start - 1
    for j in range(start, end + 1):
        if j == r:
            continue
        if l[j] <= flag:
            i += 1
            if i == r:
                i += 1
        l[i], l[j] = l[j], l[i]
    if r >= i:
        l[i + 1], l[r] = l[r], l[i + 1]
        return i + 1
    l[i], l[r] = l[r], l[i]
    return i

# use start flag as the base number
def _partation_sort4(l, start, end):
    flag = l[start]
    i = start
    j = end
    while i < j:
        while l[i] <= flag and i < j:
            i += 1
        while l[j] > flag and i < j:
            j -= 1
        l[i], l[j] = l[j], l[i]
    if l[i] <= flag:
        l[i], l[start] = l[start], l[i]
        return i
    l[i - 1], l[start] = l[start], l[i - 1]
    return i - 1

# use start flag as the base number    
def _partation_sort5(l, start, end):
    flag = l[start]
    while start < end:
        while start < end and l[end] >= flag:
            end -= 1
        l[start], l[end] = l[end], l[start]
        while start < end and l[start] <= flag:
            start += 1
        l[start], l[end] = l[end], l[start]
    return start

# normal quick sort
def quick_sort1(l, start, end):
    if start >= end:
        return l
    mid = _partation_sort1(l, start, end)
    quick_sort(l, start, mid - 1)
    quick_sort(l, mid + 1, end)
    return l

# random set before partation sort
def quick_sort2(l, start, end):
    if start >= end:
        return l
    r = random.randint(start, end)
    l[start], l[r] = l[r], l[start]

    mid = _partation_sort1(l, start, end)
    quick_sort(l, start, mid - 1)
    quick_sort(l, mid + 1, end)
    return l

在实际测试中, 由于有完全排好序的 case, 不使用随机数会因为最大递归深度限制导致测试失败

在排序完成之后, 通过一遍查找, 就能找到两个数字

def find_target(nums, target):
    i = 0
    j = len(nums) - 1
    while True:
        s = nums[i] + nums[j]
        if s == target:
            return nums[i], nums[j]
        if s < target:
            i += 1
            continue
        j -= 1

由于题目要求的是输出两个下标, 而排序已经改变了数组的原始顺序, 需要在排序前先记录一遍, 有不同的方法记录, 一个是数组拷贝, 之后再遍历查找, 需要注意一下, 同样的数字可能出现两遍, 查找的时候要注意区分, 另一个是将数组变成以 value 为 key, 下标为 value index的字典, 之后一次查找就可以, 为了处理相同的 value, 把 index 存储为数组

我们选择用字典存储, 代码会好看一点

答案

经过以上分析, 一个能通过测试的复杂度为\(O(nlgn)\)的答案为:

import random
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        l = {}
        for i in range(len(nums)):
            if nums[i] not in l:
                l[nums[i]] = [i]
            else:
                l[nums[i]].append(i)
        self.qsort(nums)
        i, j = self.find_target(nums, target)
        if len(l[i]) == 2:
            return l[i]
        if l[i][0]< l[j][0]:
            return [l[i][0], l[j][0]]
        return [l[j][0], l[i][0]] 

    def find_target(self, nums, target):
        i = 0
        j = len(nums) - 1
        while True:
            s = nums[i] + nums[j]
            if s == target:
                return nums[i], nums[j]
            if s < target:
                i += 1
                continue
            j -= 1

    def _partition_sort(self, nums, start, end):
        flag = nums[start]
        i = start
        for j in range(start + 1, end + 1):
            if nums[j] <= flag:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        nums[i], nums[start] = nums[start], nums[i]
        return i

    def _qsort(self, nums, start, end):
        if start >= end:
            return nums
        r = random.randint(start, end)
        nums[start], nums[r] = nums[r], nums[start]
        mid = self._partition_sort(nums, start, end)
        self._qsort(nums, start, mid - 1)
        self._qsort(nums, mid + 1, end)
        return nums
    def qsort(self, nums):
        if len(nums) <= 1:
            return nums
        self._qsort(nums, 0, len(nums) - 1)
打赏