算法面试题02 - 三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。

【示例】
给定数组numbers = [-1, 0, 1, 2, -1, -4]
满足要求的三元组集合为:
[[-1, 0, 1],[-1, -1, 2]]
请编写一个算法来找出给定数组中的全部三元组是否存在满足上述条件,并返回结果。
【要求】
请给出算法实现的代码，并分析算法时间和空间复杂度。

答案：

let numbers = [-1, 0, 1, 2, -1, -4]

print(threeSum(numbers))

func threeSum(_ nums: [Int]) -> [[Int]] {
    var result = [[Int]]()
    
    guard nums.count > 2 else { return result }
    
    let sortedNums = nums.sorted()
    
    for i in 0..<sortedNums.count-2 {
        if i > 0 && sortedNums[i] == sortedNums[i-1] {
            continue
        }
        var left = i + 1
        var right = sortedNums.count - 1
        while left < right {
            let sum = sortedNums[i] + sortedNums[left] + sortedNums[right]
            if sum < 0 {
                left += 1
            } else if sum > 0 {
                right -= 1
            } else {
                result.append([sortedNums[i],sortedNums[left],sortedNums[right]])
                while left < right && sortedNums[left] == sortedNums[left+1] {
                    left += 1
                }
                while left < right && sortedNums[right] == sortedNums[right-1] {
                    right -= 1
                }
                left += 1
                right -= 1
            }
        }
    }
    return result
}
//[[-1, -1, 2], [-1, 0, 1]]

知识点详解：

三元组在这个题目和通常的算法问题中，仅仅表示三个元素的组合，没有任何特殊的概念在里面。

双指针技巧固定一个指针i,左右指针初始化在两端；根据sum值判断左右指针移动方向；双指针逐渐向中间汇合。

结果集不能有重复的三元组，假如let numbers = [-1, -1, -1, 1, 2, 2]，很明显有两组三元组[-1 -1 2]。所以添加到result中后要跳过相同的左右元素进行去重！

算法思路

1. 先对数组进行排序，方便去重处理
2. 固定第一个元素,然后左右指针相向移动查找
3. 用while循环移动左右指针,计算三数之和
4. 如果和等于0就添加到结果
5. 去重逻辑:跳过相同的左元素或者右元素

算法执行过程

1. 对数组nums进行排序,时间复杂度O(nlogn)。排序后的数组方便后续去重处理。
2. 设置左右指针left和right,遍历数组nums。
3. 固定nums[i],left=i+1, right=len(nums)-1。
4. 计算sum = nums[i] + nums[left] + nums[right]。
5. 如果sum < 0,left右移一位。如果sum > 0,right左移一位。直到找到sum=0。
6. 当sum=0时,记录这个三元组。同时要跳过重复的left和right。
7. 继续遍历i,固定下一个元素,重复步骤3-6。
8. 遍历完成,返回结果res。

时间复杂度分析

三数之和算法主要包含以下步骤:

1. 对数组进行排序
   使用快速排序，时间复杂度 O(nlogn)
2. 外层for循环遍历每个元素
   遍历长度为n的数组,时间复杂度 O(n)
3. 内层while循环进行双指针操作
   左右指针遍历数组,时间复杂度也是 O(n)
4. 去重操作
   利用有序数组去重,时间复杂度 O(n)

所以总的时间复杂度为:
O(nlogn) + O(n) x O(n) + O(n) = O(nlogn + n^2) = O(n^2)
可以忽略排序的时间复杂度，整体时间复杂度约等于双指针操作的复杂度 O(n^2)。

空间复杂度分析

空间复杂度主要取决于排序所需要的栈空间，为 O(logn)。

BTW

感谢各位简友的宝贵时间与意见！文章难免有疏漏或错误，如有涉及不当之处，还望能够提出宝贵意见。感激不尽！