給定一個包含 n 個整數(shù)的數(shù)組 nums,判斷 nums 中是否存在三個元素 a,b,c ,使得 a + b + c = 0 ?找出所有滿足條件且不重復(fù)的三元組。
注意:答案中不可以包含重復(fù)的三元組。

【示例】
給定數(shù)組numbers = [-1, 0, 1, 2, -1, -4]
滿足要求的三元組集合為:
[[-1, 0, 1],[-1, -1, 2]]
請編寫一個算法來找出給定數(shù)組中的全部三元組是否存在滿足上述條件,并返回結(jié)果。
【要求】
請給出算法實現(xiàn)的代碼，并分析算法時間和空間復(fù)雜度。

答案：

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,左右指針初始化在兩端；根據(jù)sum值判斷左右指針移動方向；雙指針逐漸向中間匯合。

結(jié)果集不能有重復(fù)的三元組，假如let numbers = [-1, -1, -1, 1, 2, 2]，很明顯有兩組三元組[-1 -1 2]。所以添加到result中后要跳過相同的左右元素進(jìn)行去重！

算法思路

1. 先對數(shù)組進(jìn)行排序，方便去重處理
2. 固定第一個元素,然后左右指針相向移動查找
3. 用while循環(huán)移動左右指針,計算三數(shù)之和
4. 如果和等于0就添加到結(jié)果
5. 去重邏輯:跳過相同的左元素或者右元素

算法執(zhí)行過程

1. 對數(shù)組nums進(jìn)行排序,時間復(fù)雜度O(nlogn)。排序后的數(shù)組方便后續(xù)去重處理。
2. 設(shè)置左右指針left和right,遍歷數(shù)組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. 當(dāng)sum=0時,記錄這個三元組。同時要跳過重復(fù)的left和right。
7. 繼續(xù)遍歷i,固定下一個元素,重復(fù)步驟3-6。
8. 遍歷完成,返回結(jié)果res。

時間復(fù)雜度分析

三數(shù)之和算法主要包含以下步驟:

1. 對數(shù)組進(jìn)行排序
   使用快速排序，時間復(fù)雜度 O(nlogn)
2. 外層for循環(huán)遍歷每個元素
   遍歷長度為n的數(shù)組,時間復(fù)雜度 O(n)
3. 內(nèi)層while循環(huán)進(jìn)行雙指針操作
   左右指針遍歷數(shù)組,時間復(fù)雜度也是 O(n)
4. 去重操作
   利用有序數(shù)組去重,時間復(fù)雜度 O(n)

所以總的時間復(fù)雜度為:
O(nlogn) + O(n) x O(n) + O(n) = O(nlogn + n^2) = O(n^2)
可以忽略排序的時間復(fù)雜度，整體時間復(fù)雜度約等于雙指針操作的復(fù)雜度 O(n^2)。

空間復(fù)雜度分析

空間復(fù)雜度主要取決于排序所需要的?？臻g，為 O(logn)。

BTW

感謝各位簡友的寶貴時間與意見！文章難免有疏漏或錯誤，如有涉及不當(dāng)之處，還望能夠提出寶貴意見。感激不盡！