LeetCode 之 四数之和

前言

我们社区陆续会将顾毅(Netflix 增长黑客，数之和《iOS 面试之道》作者，数之和ACE 职业健身教练。数之和微博:@故胤道长[1])的数之和 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 17 期，数之和我们会保持更新时间和进度(周一、数之和周三、数之和周五早上 9:00 发布)，数之和每期的数之和内容不多，我们希望大家可以在上班路上阅读，数之和长久积累会有很大提升。数之和

不积跬步，数之和无以至千里;不积小流，高防服务器数之和无以成江海，数之和Swift社区 伴你前行。数之和如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

给你一个由 n 个整数组成的数组 nums，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]](若两个四元组元素一一对应，则认为两个四元组重复)：

0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

2. 示例

示例 1

输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 

示例 2

输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]] 

约束条件：

1 <= nums.length <= 200 -109 <= nums[i] <= 109 -109 <= target <= 109

3. 答案

class FourSum {      func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {          let nums = nums.sorted(by: <)         var threeSum = 0         var twoSum = 0         var left = 0         var right = 0         var res = [[Int]]()         guard nums.count >= 4 else {              return res         }         for i in 0..<nums.count - 3 {              guard i == 0 || nums[i] != nums[i - 1] else {                  continue             }             threeSum = target - nums[i]             for j in i + 1..<nums.count - 2 {                  guard j == i + 1 || nums[j] != nums[j - 1] else {                      continue                 }                 twoSum = threeSum - nums[j]                 left = j + 1                 right = nums.count - 1                 while left < right {                      if nums[left] + nums[right] == twoSum {                          res.append([nums[i], nums[j], nums[left], nums[right]])                         repeat {                              left += 1                         } while left < right && nums[left] == nums[left - 1]                             repeat {                                  right -= 1                         } while left < right && nums[right] == nums[right + 1]                     } else if nums[left] + nums[right] < twoSum {                          repeat {                              left += 1                         } while left < right && nums[left] == nums[left - 1]                     } else {                          repeat {                              right -= 1                         } while left < right && nums[right] == nums[right + 1]                     }                 }             }         }         return res     } }  主要思想：对数组进行排序并遍历，云服务器提供商根据它们的和大于或小于等于目标，向左递增或向右递减 时间复杂度：O(n^3) 空间复杂度：O(nC4)

该算法题解的仓库：LeetCode-Swift[2]

点击前往 LeetCode[3] 练习

参考资料

[1]@故胤道长:

https://m.weibo.cn/u/1827884772

[2]LeetCode-Swift:

https://github.com/soapyigu/LeetCode-Swift

[3]LeetCode:

https://leetcode.com/problems/4sum

【编辑推荐】

鸿蒙官方战略合作共建——HarmonyOS技术社区 第一个发现高危漏洞的阿里云，为什么还要被工信部暂停合作？ Python面向对象里常见的内置成员介绍 七个优秀的 Linux 滚动发行版 Linux容器与Docker的比较 Log4j一波未平，Logback 一波又起！再爆漏洞！！