求和问题总结

[toc]

题目列表

问题描述

此类题目通常情况下是给出一组 n 个数字,然后给定 target 值, 需要求出 k 个数字的 sum 为 target 的组合。此类型问题的延伸变化形式有:求 closest,求组合的个数或求组合等等。

注意事项

  • 可能有重复项,注意去掉重复的组合, 除了 2 sum 的题目最好先 sort 一下,这样可以方便去掉重复的项。
  • sort 方法枚举的时候注意不要重复,就像 subsets 一样。

一、2 sum 解法

1. 方法1:Brute Force(暴力)

枚举所有的 k-subset, 时间复杂度就是从 N 中选出 K 个,即为:$O(n^{k})$。

2.方法2:先 sort,再 two pointer

$O(NlogN + N) = O(NlogN)$,需要注意的是 sort 之后将会改变原来的顺序。

3.方法3: HashMap (O(n))

对于 2 sum 问题来说,其实就是对每个元素 nums[i],在数组中找是否存在 target - nums[i],用 HashMap 保存访问过的 value ,对每个 nums[i],检查 HashMap 中是否有 target - nums[i],扫完一遍就能够得到结果。属于用空间换时间的做法。

Time Complexity: O(n)

Space Complexity: O(n)

后续题目

对于 Two Sum 问题:

  • 如果是要返回 Index,那么优先使用 HashMap ,因为 HashMap 不会改变原来 Array 中元素的顺序。
  • 如果是返回元素的 Value, 那么可以先 Sort ,然后再使用双指针的方法来处理。

对于 Three Sum、 Three Sum Closest、 Four Sum 等问题,因为大部分都是根据 Two Sum 的双指针做法的延伸,所以都是要求返回 Value。

总结

Two Pointer(双指针)

双指针的方法有利于跳过重复元素,用来计算 Closest、Smaller 等不等于 target 的问题,此类问题优先考虑使用双指针方法。

Two Sum(Input Array is sorted)

题目描述

Array 已经 sorted。

解题思路

既然已经 sorted 那就不用再担心改变顺序,直接使用 Two Pointer 方法来做就行。

Solution 1:(Two Pointer)

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(numbers)
        if length < 2:
            return []
        #sort to allow two-pointer algorithm and skip duplicate
        numbers.sort()
        start, end = 0, length - 1
        while start < end:
            #skip duplicate elements
            if start != 0 and numbers[start] == numbers[start-1]:
                start += 1
            elif end != length - 1 and numbers[end] == numbers[end+1]:
                end -= 1
            else:
                curSum = numbers[start] + numbers[end]
                if curSum == target:
                    return [start + 1, end + 1]
                elif curSum < target:
                    start += 1
                else:
                    end -= 1
        return []

Solution 2:(Binary Search)

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        length = len(numbers)
        if length < 2:
            return [0, 0]
        index1 = 0
        index2 = 0
        for i, num in enumerate(numbers):
            foundPair, index = self.search(i + 1, length - 1, numbers, target - num)
            if foundPair:
                index1 = i + 1
                index2 = index + 1
                return [index1, index2]
        return [index1, index2]
    
    def search(self, start, end, numbers, t):
        while start + 1 < end:
            mid = start + (end - start) / 2
            if numbers[mid] == t:
                return True, mid
            elif numbers[mid] < t:
                start = mid
            else:
                end = mid
        if numbers[start] == t:
            return True, start
        if numbers[end] == t:
            return True, end
        return False, 0

二、3 sum 解法

Three Sum 问题可以退化为 Two Sum 问题,先取出一个数 i,然后在剩下的数组中找 sum 为 target - i 的组合就可以了。

这里需要注意的是不管采用 sort 还是 HashMap 的方法,时间复杂度其实都是 $O(n^{2})$。HashMap 的解法已经介绍过来,排序的解法如下:

排序:

只需要 sort 一遍 $O(nlogn)$,然后每次取出一个数,再使用 Two Pointer 方法寻找的复杂度为 $O(n^2)$,总的时间复杂度为:$O(nlogn + n^2) = O(n^2)$。

题目描述

Given an array S of n integers, are there elements a, b, c in S such that a + b + c
= 0?

Last modification:September 24th, 2019 at 03:44 pm
如果觉得我的文章对你有用,请随意赞赏