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

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]