給定一個包含 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)行去重犯戏！
算法思路
- 先對數(shù)組進(jìn)行排序送火，方便去重處理
- 固定第一個元素,然后左右指針相向移動查找
- 用while循環(huán)移動左右指針,計算三數(shù)之和
- 如果和等于0就添加到結(jié)果
- 去重邏輯:跳過相同的左元素或者右元素
算法執(zhí)行過程
- 對數(shù)組nums進(jìn)行排序,時間復(fù)雜度O(nlogn)。排序后的數(shù)組方便后續(xù)去重處理先匪。
- 設(shè)置左右指針left和right,遍歷數(shù)組nums种吸。
- 固定nums[i],left=i+1, right=len(nums)-1。
- 計算sum = nums[i] + nums[left] + nums[right]呀非。
- 如果sum < 0,left右移一位坚俗。如果sum > 0,right左移一位。直到找到sum=0岸裙。
- 當(dāng)sum=0時,記錄這個三元組猖败。同時要跳過重復(fù)的left和right。
- 繼續(xù)遍歷i,固定下一個元素,重復(fù)步驟3-6降允。
- 遍歷完成,返回結(jié)果res恩闻。
時間復(fù)雜度分析
三數(shù)之和算法主要包含以下步驟:
- 對數(shù)組進(jìn)行排序
使用快速排序，時間復(fù)雜度 O(nlogn) - 外層for循環(huán)遍歷每個元素
遍歷長度為n的數(shù)組,時間復(fù)雜度 O(n) - 內(nèi)層while循環(huán)進(jìn)行雙指針操作
左右指針遍歷數(shù)組,時間復(fù)雜度也是 O(n) - 去重操作
利用有序數(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ù)雜度主要取決于排序所需要的棧空間送滞，為 O(logn)侠草。
BTW
感謝各位簡友的寶貴時間與意見！文章難免有疏漏或錯誤犁嗅，如有涉及不當(dāng)之處边涕，還望能夠提出寶貴意見。感激不盡褂微！
