算法面试真题详解：最接近的三数之和

描述
给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。
只需要返回三元组之和，无需返回三元组本身

在线评测地址：领扣题库官网

样例1
输入:[2,7,11,15],3
输出:20
解释:
2+7+11=20

        

          
        
        
        

          

          AI 代码解读
        
      
      

样例2
输入:[-1,2,1,-4],1
输出:2
解释:
-1+2+1=2

        

          
        
        
        

          

          AI 代码解读
        
      
      

解法思路

• 本题是57. 三数之和的扩展问题，不再要求恰好相等，而是找与target最接近的三数之和。
• 本题需要计算三数之和，如果用暴力枚举，时间复杂度会是O(n3)O(n3)。我们这里采用双指针的方法，来降低时间复杂度。首先将数组排序，然后固定一个数numbersi上用双指针来找与target最接近的三数之和nearest。
  算法流程
• 第一步，对数组进行排序。只有将数组转化为有序数组，我们才方便移动双指针。
• 第二步，在数组numbers中遍历，每次固定numbers[i]作为第一个数
  • 建立双指针left和right，初始化分别指向i + 1和len(numbers) - 1
• 求出此时的三数之和curr，如果curr和target恰好相等，我们可以直接返回target。
• 比较curr和nearest谁距离target更近，如果是curr，那么将nearest更新为target
• 判断curr和target的大小关系，如果curr > target，那么right左移；反之，left右移。继续第二步的过程，直到left >= right。
• 此外，当数组中有重复元素时，为了避免重复运算，在代码中添加了三处剪枝操作。当指针指向新的位置和旧的位置的值相等时，我们继续移动指针。
  算法复杂度
• 时间复杂度
  • 数组排序的时间复杂度为O(nlogn)O(nlogn)
• 遍历过程，固定值为 n 次，双指针为 n 次，时间复杂度为 O(n2))O(n2))
• 总时间复杂度：O(nlogn)+O(n2)=O(n2)O(nlogn)+O(n2)=O(n2)
• 空间复杂度为O（1），只需要常量空间。

  class Solution:
  """
  @param numbers: Give an array numbers of n integer
  @param target: An integer
  @return: return the sum of the three integers, the sum closest target.
  """
  def threeSumClosest(self, numbers, target):
      nearest = float('inf')
      # step1: 首先对数组进行排序
      numbers = sorted(numbers)
      # step2: 遍历
      for i in range(len(numbers) - 2):
          # 剪枝1
          if (i > 0 and numbers[i] == numbers[i - 1]):
              continue
          # 定义双指针
          left = i + 1
          right = len(numbers) - 1
          # 双指针相向而行
          while (left < right):
              # 此时的三数之和
              curr = numbers[left] + numbers[right] + numbers[i]
              # 和恰好为target
              if curr == target:
                  return target
              # 更新 nearest
              if abs(curr - target) < abs(nearest - target):
                  nearest = curr
              # 移动双指针
              if curr > target:
                  right -= 1
                  # 剪枝2
                  while (right >= 0 and numbers[right] == numbers[right + 1]):
                      right -= 1
              else:
                  left += 1
                  # 剪枝3
                  while (left < len(numbers) and numbers[left] == numbers[left - 1]):
                      left += 1
      return nearest
  
          
  
            
          
          
          
  
            
  
            AI 代码解读
          
        
        

更多题解参考：九章官网solution