LeetCode 259 题全剖析：Swift 快速找出“满意条件”的三人组 ...

  
择要

本文围绕 LeetCode 259 题“较小的三数之和”，通过 Swift 给出两种解法，并团结双指针的优化思绪，讲清楚这类“数组 + 条件组合”类题目常见的办理套路。同时附上可运行 Demo，资助你快速上手并掌握三数题目标变种场景。

描述

题目要求：
给定一个整数数组 nums，以及一个目标值 target，请你统计在所有不同的三元组 (i, j, k) 中，满意：

1. nums[i] + nums[j] + nums[k] < target 且 i < j < k

复制代码

的组合总数，并返回这个值。
示例 1：

1. 输入: nums = [-2, 0, 1, 3], target = 2  
2. 输出: 2  
3. 解释: 满足的组合有 (-2, 0, 1) 和 (-2, 0, 3)

复制代码

示例 2：

1. 输入: nums = [], target = 0  
2. 输出: 0

复制代码

示例 3：

1. 输入: nums = [0], target = 0  
2. 输出: 0

复制代码

题解答案（Swift）

这道题其实是“三数和”的一个变种，只不过目标变成了 < target，不再是 == 0。最直观的解法是暴力三重循环，但效率感人，时间复杂度是 O(n³)。这里我们采用排序 + 双指针的思绪，降低时间复杂度。
题解代码分析

1. func threeSumSmaller(_ nums: [Int], _ target: Int) -> Int {
2.     let sorted = nums.sorted()
3.     var count = 0
4.    
5.     for i in 0..<sorted.count - 2 {
6.         var left = i + 1
7.         var right = sorted.count - 1
8.         
9.         while left < right {
10.             let sum = sorted[i] + sorted[left] + sorted[right]
11.             if sum < target {
12.                 // 所有 [left, right) 的组合都满足条件
13.                 count += right - left
14.                 left += 1
15.             } else {
16.                 right -= 1
17.             }
18.         }
19.     }
20.    
21.     return count
22. }

复制代码

示例测试及结果

1. print(threeSumSmaller([-2, 0, 1, 3], 2))  // 输出：2
2. print(threeSumSmaller([], 0))            // 输出：0
3. print(threeSumSmaller([0], 0))           // 输出：0
4. print(threeSumSmaller([1, 2, 3, 4, 5], 9)) // 输出：4

复制代码

解释：

• 对于 [1,2,3,4,5]，满意三数和 < 9 的组合有：
  
  
  
  • 1+2+3=6
    
  • 1+2+4=7
    
  • 1+2+5=8
    
  • 1+3+4=8
    
  
  

共 4 个。
时间复杂度

• 排序需要 O(n log n)
  
• 主循环是 O(n²)
  

整体时间复杂度：O(n²)，比暴力三重循环好很多。
空间复杂度

• 排序用了额外空间（大概是快排的栈）
  
• 紧张是常数级别的变量，没有使用额外数组
  

空间复杂度：O(1)（不考虑排序时的栈开销）
总结

这题其实属于“三数题目”的系列题目，只不过目标条件从 == target 变成了 < target。一旦习惯了排序 + 双指针的套路，这类题目处理起来就非常顺手了。
也建议大家实行思考下另外两个方向：

• 假如是 > 怎么办？
  
• 假如不能排序怎么办？
  

另外也可以思考怎么把这类题目封装成通用的“多数和小于目标”的函数，能提拔在面试中的发挥空间。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。