LeetCode 259 题全剖析：Swift 快速找出“满意条件”的三人组
https://i-blog.csdnimg.cn/direct/565ae998d0be43cb80d488f660a12704.png#pic_centerhttps://i-blog.csdnimg.cn/blog_migrate/aadffb113c7529bb0a991c3f73e8f846.gif
择要
本文围绕 LeetCode 259 题“较小的三数之和”，通过 Swift 给出两种解法，并团结双指针的优化思绪，讲清楚这类“数组 + 条件组合”类题目常见的办理套路。同时附上可运行 Demo，资助你快速上手并掌握三数题目标变种场景。
https://i-blog.csdnimg.cn/direct/033fb49516be49f08d7533c3cc0df26d.png
描述
题目要求：
给定一个整数数组 nums，以及一个目标值 target，请你统计在所有不同的三元组 (i, j, k) 中，满意：
nums + nums + nums < target 且 i < j < k
的组合总数，并返回这个值。
示例 1：
输入: nums = [-2, 0, 1, 3], target = 2
输出: 2
解释: 满足的组合有 (-2, 0, 1) 和 (-2, 0, 3)
示例 2：
输入: nums = [], target = 0
输出: 0
示例 3：
输入: nums = , target = 0
输出: 0
https://i-blog.csdnimg.cn/direct/a0d338fa17054066953ec43bb8f178a1.png
题解答案（Swift）
这道题其实是“三数和”的一个变种，只不过目标变成了 < target，不再是 == 0。最直观的解法是暴力三重循环，但效率感人，时间复杂度是 O(n³)。这里我们采用排序 + 双指针的思绪，降低时间复杂度。
题解代码分析
func threeSumSmaller(_ nums: , _ target: Int) -> Int {
let sorted = nums.sorted()
var count = 0
for i in 0..<sorted.count - 2 {
var left = i + 1
var right = sorted.count - 1
while left < right {
let sum = sorted + sorted + sorted
if sum < target {
// 所有 [left, right) 的组合都满足条件
count += right - left
left += 1
} else {
right -= 1
}
}
}
return count
}
示例测试及结果
print(threeSumSmaller([-2, 0, 1, 3], 2))// 输出：2
print(threeSumSmaller([], 0)) // 输出：0
print(threeSumSmaller(, 0)) // 输出：0
print(threeSumSmaller(, 9)) // 输出：4
解释：
[*]对于 ，满意三数和 < 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企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]