Swift 算法俱乐部：3Sum 与 4Sum 问题全解析——基于排序与双指针的 Swift 通用解法

Swift 算法俱乐部3Sum 与 4Sum 问题全解析——基于排序与双指针的 Swift 通用解法【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club导读3Sum三数之和与 4Sum四数之和是经典算法题 Two-Sum Problem两数之和的扩展要求从整数数组中找出所有和为指定目标值的三元组 / 四元组且结果中不得出现重复组合。本文以本仓库 3Sum and 4Sum 文档为核心深入讲解「先排序 双指针逼近 相邻去重」这一高效解法并给出可直接在 Playground 运行的完整 Swift 泛型实现。读完本文你将掌握如何把两数之和的算法思想推广到任意 k 数之和并理解如何用 Swift 标准库协议BidirectionalCollection、Numeric、Comparable写出与元素类型无关的通用解法。问题定义从两数之和到三数、四数之和原文档开篇即点明3Sum 与 4Sum 是经典算法题 2Sum 的扩展。3Sum给定一个整数数组找出数组中所有由 3 个值组成的子集使得这 3 个值之和等于目标值。注意解集中不能包含重复的三元组。例如给定数组[-1, 0, 1, 2, -1, -4]目标值0解集为[[-1, 0, 1], [-1, -1, 2]]——数组中的两个-1被视为不同的元素。4Sum给定一个包含 n 个整数的数组 S找出所有由 4 个值组成的子集使得这 4 个值之和等于目标值。注意解集中不能包含重复的四元组。值得强调的是「去重」的含义[-1, 0, 1]与[0, 1, -1]这类仅仅顺序不同的组合只算一种而数组中出现多次的相同数值如示例中的两个-1分别可以参与构成不同的三元组[-1, 0, 1]和[-1, -1, 2]。这就要求算法既能枚举所有可能组合又能剔除值相同的重复组合。在深入 3Sum 之前有必要回顾一下 2Sum 的双指针思路因为它是整个解法的基石。在 Two-Sum Problem 的 Solution 2 中先对数组排序再用i、j两个指针分别指向数组首尾根据a[i] a[j]与目标值k的大小关系决定移动左指针还是右指针从而在O(n)时间内找到答案若包含排序则整体为O(n log n)且无需额外存储。3Sum 正是把这一「双指针逼近」思想内嵌到外层循环中。两大关键前提排序与去重原文档指出解决 3Sum 有 2 个关键步骤对数组排序Sorting与避免重复Avoiding Duplicates。排序带来的强大假设对输入数组进行排序后可以得出两条有力的结论重复元素总是彼此相邻——这为跳过重复值提供了便利索引右移值增大索引左移值减小——这使得我们可以像 2Sum 那样根据当前和与目标值的大小关系决定性地移动某个指针而不是盲目枚举。这两条规则是下面高效算法的根基。排序本身由 Swift 标准库的sorted()完成时间复杂度为O(n log n)。相邻去重formUniqueIndex 辅助方法由于预先排序重复元素必然相邻因此只需在遍历时比较相邻值即可跳过重复。原文档给出了两个基于 Swift 集合协议的通用去重辅助方法在 3Sum.playground 与 4Sum.playground 中均有完整源码extension Collection where Element: Equatable { /// In a sorted collection, replaces the given index with a successor mapping to a unique element. /// /// - Parameter index: A valid index of the collection. index must be less than endIndex func formUniqueIndex(after index: inout Index) { var prev index repeat { prev index formIndex(after: index) } while index endIndex self[prev] self[index] } }该方法作用于已排序的集合从index出发不断向后推进直到指向的元素与上一个不同为止。repeat-while保证index至少前进一位避免死循环index endIndex防止越界。它就地修改传入的indexinout参数返回的索引指向一个新的、与之前不同的元素。与之对称还有一个向前向左移动的版本适用于BidirectionalCollectionextension BidirectionalCollection where Element: Equatable { /// In a sorted collection, replaces the given index with a predecessor that maps to a unique element. /// /// - Parameter index: A valid index of the collection. index must be greater than startIndex. func formUniqueIndex(before index: inout Index) { var prev index repeat { prev index formIndex(before: index) } while index startIndex self[prev] self[index] } }注意两个方法约束的协议不同向后移动只需Collection单向遍历能力而向前移动要求BidirectionalCollection可双向遍历。这一点与后续算法函数签名中的BidirectionalCollection约束相互呼应。3Sum 算法三指针拼装三元组原文档用图示直观展示了三个索引的协作关系。以示例数组排序后[-4, -1, -1, 0, 1, 2]为例m - - r [-4, -1, -1, 0, 1, 2] ll是外层循环指针遍历整个数组代表三元组中的第一个数m从l的后一个位置开始向左后移动r指向数组末尾向前左移动。任意时刻三数之和为array[l] array[m] array[r]。整体思路是固定l对l之后的子数组应用 2Sum 算法——这正应了原文档所说的「只要熟悉 2Sum前提就非常直白」。完整实现如下源码见 3Sum.playground/Contents.swiftfunc threeSumT: BidirectionalCollection(_ collection: T, target: T.Element) - [[T.Element]] where T.Element: Numeric Comparable { let sorted collection.sorted() var ret: [[T.Element]] [] var l sorted.startIndex ThreeSum: while l sorted.endIndex { defer { sorted.formUniqueIndex(after: l) } var m sorted.index(after: l) var r sorted.index(before: sorted.endIndex) TwoSum: while m r r sorted.endIndex { let sum sorted[l] sorted[m] sorted[r] if sum target { ret.append([sorted[l], sorted[m], sorted[r]]) sorted.formUniqueIndex(after: m) sorted.formUniqueIndex(before: r) } else if sum target { sorted.formUniqueIndex(after: m) } else { sorted.formUniqueIndex(before: r) } } } return ret }逐行拆解执行逻辑排序let sorted collection.sorted()为后续所有去重与指针移动操作建立前提。外层循环ThreeSumwhile l sorted.endIndex遍历第一个数。defer { sorted.formUniqueIndex(after: l) }是点睛之笔——defer保证每次循环体结束时无论经过哪条分支l都会前进到下一个不重复的位置从而从根上杜绝以相同l值开头的重复三元组。初始化双指针m sorted.index(after: l)l后一位r sorted.index(before: sorted.endIndex)最后一个元素。内层循环TwoSumwhile m r r sorted.endIndex保证指针不越界、不相交。计算三数之和并分三种情况处理sum target找到一组解ret.append([sorted[l], sorted[m], sorted[r]])随后m、r各自移动到下一个唯一值继续向内收缩寻找更多解sum target和太小说明需要更大的数将m右移formUniqueIndex(after: m)增大和sum target和太大将r左移formUniqueIndex(before: r)减小和。这里所有指针移动都使用formUniqueIndex系列方法确保任何索引位置的取值都不会与上一轮重复配合外层defer去重最终返回的解集天然满足「无重复三元组」的要求。从源码可见的测试样例3Sum.playground/Contents.swift 内置了三组可直接运行的验证样例展示了不同重复形态下的去重行为// Answer: [[-1, 0, 1], [-1, -1, 2]] threeSum([-1, 0, 1, 2, -1, -4], target: 0) // Answer: [[-1, -1, 2], [-1, 0, 1]] threeSum([-1, -1, -1, -1, 2, 1, -4, 0], target: 0) // Answer: [[-1, -1, 2]] threeSum([-1, -1, -1, -1, -1, -1, 2], target: 0)第三组样例尤其能检验去重逻辑数组中连续出现 6 个-1正确输出只有一个[-1, -1, 2]——因为任意两个-1与2组合成的三元组值相同只能保留一个。这正是相邻去重策略的价值所在。复杂度分析从代码结构可以推断外层循环l遍历n个去重后的位置内层m、r双指针在剩余区间内最多各移动n次因此算法主体为O(n²)排序额外花费O(n log n)故总体时间复杂度为O(n²)。辅助空间方面除结果数组外仅需常数级指针变量与排序副本为O(n)含排序副本或 O(1)不计输出。4Sum 算法四指针的递归式扩展原文档指出4Sum 是 3Sum 非常直接的扩展3Sum 维护 3 个索引4Sum 则维护 4 个mr - - r [-4, -1, -1, 0, 1, 2] l ml -l与ml构成双层外层循环分别对应四元组的前两个数mr从ml后一位开始向右移动r从末尾向左移动内层mr、r双指针依然执行两数之和的逼近逻辑。也就是说4Sum 外层遍历第 1 个数 × 中层遍历第 2 个数 × 内层对剩余区间做 2Sum。完整实现如下源码见 4Sum.playground/Contents.swiftfunc fourSumT: BidirectionalCollection(_ collection: T, target: T.Element) - [[T.Element]] where T.Element: Numeric Comparable { let sorted collection.sorted() var ret: [[T.Element]] [] var l sorted.startIndex FourSum: while l sorted.endIndex { defer { sorted.formUniqueIndex(after: l) } var ml sorted.index(after: l) ThreeSum: while ml sorted.endIndex { defer { sorted.formUniqueIndex(after: ml) } var mr sorted.index(after: ml) var r sorted.index(before: sorted.endIndex) TwoSum: while mr r r sorted.endIndex { let sum sorted[l] sorted[ml] sorted[mr] sorted[r] if sum target { ret.append([sorted[l], sorted[ml], sorted[mr], sorted[r]]) sorted.formUniqueIndex(after: mr) sorted.formUniqueIndex(before: r) } else if sum target { sorted.formUniqueIndex(after: mr) } else { sorted.formUniqueIndex(before: r) } } } } return ret }与原文档描述一致它与threeSum的结构高度相似差异仅在于多了一层ml循环ThreeSum标签对应四元组的第二个数内层和的表达式变为四项sorted[l] sorted[ml] sorted[mr] sorted[r]命中目标时追加的是四个元素组成的数组。l与ml两个外层循环均使用defer { sorted.formUniqueIndex(...) }去重内层mr、r同样使用唯一索引移动因此四元组同样不会重复。从源码可见的测试样例4Sum.playground/Contents.swift 内置了 LeetCode 风格的经典样例// answer: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] fourSum([1, 0, -1, 0, -2, 2], target: 0)注意该样例中包含重复值0输出中[-2, 0, 0, 2]与[-1, 0, 0, 1]都使用了两个0——它们分别来自数组中的两个不同0元素同时[-2, 0, 0, 2]不会被重复输出多次体现了去重逻辑的正确性。复杂度分析从代码结构看外层两层循环各约n次迭代内层双指针合计约n次移动因此 4Sum 的时间复杂度为O(n³)排序的O(n log n)可忽略辅助空间同样为常数级加排序副本。推广模式k-Sum 家族的统一结构对比threeSum与fourSum的源码可以发现一个清晰的递推模式2Sum一对双指针(i, j)逼近目标3Sum固定 1 个数剩余区间做 2Sum4Sum固定 2 个数剩余区间做 2Sum。每增加一个数就多一层外层循环、多一个defer去重点而最内层永远是「双指针 三分支判断」。由此可以推断kSum 问题k ≥ 2可用「排序 (k-2) 层固定循环 一层双指针」解决时间复杂度为O(n^(k-1))。这个统一结构正是理解 3Sum / 4Sum 及其变体的核心心智模型。泛型设计要点约束与复用两个函数均采用 Swift 泛型签名值得专门分析其约束含义func threeSumT: BidirectionalCollection(_ collection: T, target: T.Element) - [[T.Element]] where T.Element: Numeric ComparableT: BidirectionalCollection函数需要sorted.formUniqueIndex(before:)而该辅助方法要求BidirectionalCollection可向后遍历因此函数体级别必须保证这一能力T.Element: Numeric允许对元素执行运算T.Element: Comparable允许执行、比较用于判断和与目标值的大小关系也保证sorted()可用。这三个约束共同保证了函数对Int、Double等任意数值类型均适用而不是把算法写死为[Int]。这正是 Swift 集合协议 泛型约束组合出的高复用性写法。如何在 Playground 中运行验证仓库为每个算法都提供了独立的 Playground运行方式与普通 Swift Playground 一致打开 3Sum.playground 或 4Sum.playground两个 Playground 均适配 Swift 4.2文件头部的#if swift(4.2)判断可忽略在 Xcode 中打开并运行Playground 的侧边栏会显示每次调用的返回值即可直接核对文档中标注的期望输出也可以自行追加新的调用例如threeSum([-2, 0, 1, 1, 2], target: 0) fourSum([-3, -2, -1, 0, 0, 1, 2, 3], target: 0)验证返回结果中不含重复三元组 / 四元组。仓库根目录 README.markdown 的算法索引中本主题登记为Three-Sum/Four-Sum Problem与其他算法如 Two-Sum Problem、Binary Search 等并列便于按图索骥查阅相关实现。总结3Sum 与 4Sum 的解法精髓可以浓缩为三句话排序先行让重复值相邻、让指针移动方向与值的大小方向一致一切后续操作都建立在这个前提之上双指针逼近内层始终复用 2Sum 的三分支判断等于 / 小于 / 大于以 O(n) 时间扫描区间相邻去重借助formUniqueIndex(after:)/formUniqueIndex(before:)与defer机制让每个索引在每轮循环后都跳到下一个唯一值从而保证输出解集无重复。本仓库的 3Sum and 4Sum/README.md、3Sum.playground 与 4Sum.playground 提供了完整的实现与可运行样例是理解 k-Sum 问题家族、练习排序 双指针范式的理想参考。本文内容基于 Swift Algorithm Club 仓库 3Sum and 4Sum 文档整理原作者为 Kai Chen 与 Kelvin Lau。【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考