利扣两数之和/三数之和/最接近三数之和解题思路

发布于:2022-11-07 ⋅ 阅读:(10) ⋅ 点赞:(0) ⋅ 评论:(0)

2数之和

题干

在这里插入图片描述

理解题干
  1. 入参有2个变量,整数数组,目标值
  2. 因为没有特别说明,默认数组是无序的,允许有重复值的,可能存在负数,元素可以为0
  3. 要求找出数组中不同位置的一对数值,两数之和为目标值
  4. 输出结果类型为数组,内元素表示的所选的2个元素 的下标索引
  5. 数组内只有一对答案符合要求,即找到符合要求的答案即可返回
  6. 返回的数组内的下标索引不要求前后顺序
解题思路
  1. 是否需要对数组排序: 因为要返回数组下标,且存在重复元素,通过理解题干,不能对数组排序
  2. 暴力的解法: 通过固定一个元素,得出与目标值的差值,检查后续的元素是否与此值相等,相等则返回当前元素和另一个元素的索引值
  3. 暴力解法的问题:时间复杂度为O(n^2)
  4. 优化思路:使用哈希表数据结构(字典),以key作为差值,value作为当前元素的索引,每便利一个元素就保存一个k-v键值对,后续的元素只需要检查当前值是否在字典中即可,时间复杂度O(n)
代码实现
class Solution:
    def twoSum(self, nums, target):
        temp = {}
        for i,num in enumerate(nums):
            if temp.get(num) is not None:  
              # 注意此处字典.get()不存在key返回None,当key存在且值为0时属于正常情况,但若只写
              # temp.get(num),则也会被当作False条件,所以要明确 is not None
                return [i, temp[num]]
            minus = target-num
            temp.update({minus:i})
        return []

3数之和

题干

在这里插入图片描述

理解题干
  1. 入参有1个变量,整数数组
  2. 要求从中去三个不同位置的元素,三数之和为0
  3. 返回一个数组,其中包含所有符合条件的三元组,三元组内元素顺序没有要求,所以不能有重复的三元组
  4. 三元组在外层数组内的位置不用关心
  5. 可能没有目标三元组,即可能返回空列表
解题思路
  1. 是否可以借鉴2数之和的思路:确定当前值之后,仍然需要再确定2个值才能符合要求,这对于哈希表并不容易实现
  2. 尝试使用暴力解法:遍历数组的元素,确定当前值,然后再确定其之后的第二个值,再继续便利从第三个值开始的剩余值,判断三个数之和是否为0,如果为0则保存到结果列表中,直到所有值遍历完毕
  3. 暴力解法的缺点:三层循环,时间复杂度O(n^3)
  4. 优化点:是否需要给数组排序,排序后会发现,要达到目标值为0的目的,要么三元组全为0,要么一定存在正数和负数。当前值为负数的时候,肯定需要一个正数,这个正数最大的在排序后数组的最右,两数相加,如果结果为正数,说明需要再取一个负数抵消,如果结果为负数,需要再取一个正数抵消。且当前值作为排序后的元素,如果已经>0,则无需继续判断后续的数值,因为后续的值和当前值和肯定>0。利用这些规则,可以减少一些不必要的遍历(如三个数都是负数或三个数都是正数的情况)
  5. 遍历过程中会涉及三个索引位置,所以需要定义三个指针(索引位)
代码实现
class Solution:
    def threeSum(self, nums):
      result = []
      nums.sort()
      for i,num in enumerate(nums):
        if num>0:
          return result
        curr_index = i
        right = len(nums) - 1
        left = curr_index + 1
        while left<right:
          if num+nums[left]+nums[right]>0:
            right -= 1
          elif num+nums[left]+nums[right]<0:
            left += 1
          elif num+nums[left]+nums[right]==0:
            result.append([num, nums[left], nums[right]])
            left += 1
            right -= 1
      return result

运行以上代码测试会发现结果正常输出,但结果可能存在相同的三元组,所以需要增加去重的逻辑

class Solution:
    def threeSum(self, nums):
        result = list()
        nums.sort()
        temp=set()  # 使用集合保存结果
        for i, num in enumerate(nums):
            if num > 0:
                return result
            curr_index = i
            right = len(nums) - 1
            left = curr_index + 1
            while left < right:
                if num + nums[left] + nums[right] > 0:
                    right -= 1
                elif num + nums[left] + nums[right] < 0:
                    left += 1
                elif num + nums[left] + nums[right] == 0:
                    if (num, nums[left], nums[right]) not in temp:  
                      # 判断新值是否在集合中,使用in的算法复杂度较高,但能实现
                        result.append([num, nums[left], nums[right]])
                        temp.add((num, nums[left], nums[right]))
                    left += 1
                    right -= 1
        return result

以上结果已经可以正常交作业,但在利扣上对下会发现排名超级靠后,所以肯定还有更优的解题方法

查看排名较靠前的记录,发现最优解使用了一些特殊的包如 bisect,主要用以对有序数组的操作,但大多数人可能并不知道有这样的包,有没有不适用特殊包处理的方案,查到另一位的思路很不错,请看代码

class Solution:
    def threeSum(self, nums):
        res = []
        d = dict()
        for i in nums:
            d[i] = d.get(i, 0) + 1
        po = [x for x in d if x > 0]
        ne = [x for x in d if x < 0]
        if d.get(0, 0) > 2:
            res.append([0, 0, 0])  # 三个值全相等

        for p_num in po:  # 正数数组
            for n_num in ne:  # 负数数组
                target = -(p_num + n_num)  # 目标第三值
                if target in d:
                    if target == p_num and d[target] > 1:
                        res.append([p_num, p_num, j])  # 有两个负值相等
                    if target == n_num and d[target] > 1:
                        res.append([p_num, n_num, n_num])  # 有两个正值相等
                    if p_num > target > n_num:
                        res.append([p_num, target, n_num])  # 三个值都不相等
        return res


if __name__ == '__main__':
    print(Solution().threeSum([-1, 0, 1, 1, 2, -1, -4]))
    # >> [[1, 0, -1], [2, -1, -1]]

此方法精妙之处在于把负数和正数经过去重分开处理(体现了分而治之的思想),且保留了数组中元素的个数信息(通过哈希表(字典)),然后将结果分为3类,一类是所有值都相等,只有一种情况是[0,0,0],其中2个值相等,条件是nums中会存在至少2个这样的值,因为做过了去重,所以不会担心遍历到相同的情况。三个值都不相等情形最普通,整体逻辑非常清晰易懂,算法复杂度是O(n^2)

最接近的3数之和

题干

在这里插入图片描述

理解题干
  1. 输入变量有2个,整数数组,目标值
  2. 要求从数组中选出3个不同位置的元素,使三数之和与目标值的差值(距离)最小
  3. 返回此3个数的和值
  4. 答案唯一,即只有一个最有解
  5. 因为没有特殊说明,数组中可能会有重复值,数组无序
解题思路
  1. 跟3数之和有什么区别:三数之和要求和值一定为0,条件比较确定。本题要求最接近,条件不是特别确定。但3数之和的3元组有多组的情况,而本题只有一个解,相较又减少了复杂系数
  2. 数组是否需要排序: 因为结果中并没有与元素坐标相关的条件或要求,所以可以先排序
  3. 尝试暴力解法: 仍然需要维护3个指针,从左向右遍历,不过三数之和的比较对象不再是0,而是target 目标值,不论和值大于目标值还是小于目标值,都需要记录此差值(距离),当等于目标值的时候,肯定距离最小且答案唯一,可直接返回。既然答案唯一,隐藏的条件是任意三数之和与target的距离差值,也是唯一的,这个特性可以联想到使用哈希表的key作为存储结构,value就是三数之和的实际值, 最终只需使用min()方法,找到最小的key即可
代码实现
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        result = {}
        i = 0
        if nums[0]+nums[1]+nums[2]>target:  # 特殊情况可以提前返回
            return nums[0]+nums[1]+nums[2]
        if nums[-1] + nums[-2]+nums[-3]<target:
            return nums[-1] + nums[-2]+nums[-3]
        while i<=len(nums)-3:
            j = i+1
            k = len(nums)-1
            while j< k:
                v = nums[i]+nums[j]+nums[k]
                if v>target:
                    result.update({v-target:v})
                    k-=1
                elif v<target:
                    result.update({target-v: v})
                    j+=1
                elif v==target:
                    return v
            i+=1
        r = min(result
        return result[r]