Two Sum

  • 问题描述:

给定一个整型的数组,返回和为指定值的两个元素的下标,可以假设只有一个答案。

这个问题写出解决代码很简单,第一想法就是两层遍历,先遍历前len(nums)-1个元素,再遍历对应的剩余元素。这种解法很直白,但是时间复杂度为O(n*n), 果然是提示时间超限的,所以要想办法降低时间复杂度。

如果引入一个存储已经遍历元素的buffer dict就能将时间复杂度降为O(n), 具体代码如下:

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) <= 1:
            return False
        buff_dict = {}
        for i in range(len(nums)):
            if nums[i] in buff_dict:
                return [buff_dict[nums[i]], i]
            else:
                buff_dict[target - nums[i]] = i
  • 代码分析: 使用 buff_dict 存储已经遍历过的元素以及与该元素的和为制定值的解,这样的话如果以后遍历的元素为已经遍历的元素的解,那么这个元素就已经在字典里了。

3Sum

  • 问题描述:

给定一个整型数组,检测其中是否有三个元素的和为 0,返回所有符合要求的三个元素组成的数组。

在解决这个问题时,如果想起了 Two Sum 的解法,可能就会走弯路了。下面上时间复杂度为O(n*n)的解法:

class Solution():
    def threeSum(self, nums):
        nums.sort()
        res = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                sum_result = nums[i] + nums[l] + nums[r]
                if sum_result < 0:
                    l = l + 1
                elif sum_result > 0:
                    r = r - 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]:
                        l += 1
                    while l < r and nums[r] == nums[r-1]:
                        r -= 1
                    l += 1; r -= 1
        return res
  • 代码分析: 没有什么好说的,这种问题就应该用这种解法,简单明了。

3Sum Closest

  • 问题描述: 给定一个整型数组,找到数组中的三个元素,使三者的和最接近与一个给定值。返回三者的和。可以假设满足要求的元素只有一组。

这个问题和3Sum问题解法一样,下面上时间复杂度为O(n*n)的解法:

class Solution(object):
    def threeSumClosest(self, nums, target):
        if len(nums) < 3:
            return None
        nums.sort()
        res = nums[0] + nums[1] + nums[2]
        for i in range(len(nums)-2):
            l, r = i+1, len(nums)-1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s == target:
                    return  s
                if abs(s - target) < abs(res - target):
                    res = s
                if s < target:
                    l += 1
                elif s > target:
                    r -= 1
        return res

要耳聪目明才能吃嘛嘛香啊!