IT评测·应用市场-qidao123.com技术社区

标题: LeetCode 259 题全剖析：Swift 快速找出“满意条件”的三人组 [打印本页]
作者: 徐锦洪    时间: 2025-4-19 21:54
标题: 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
复制代码
解释：

共 4 个。
时间复杂度


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


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

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

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

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



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4