IOS 算法 三數之和求解問題
IOS 算法三數之和求解問題
1、三數求和簡單介紹
對於一個整數的數組, 是否存在a, b, c 使得 a + b + c = 0, 返回a b c 數組,相同數組隻返回一個,:
例如:
[-1, -2, 6, 5, 0, 1, 2, -1, -1] 返回 [[-1, 0, 1], [-2, 0, 2], [-1, -1, 2]]
關鍵點:
① 找到和為0的三個數
② 去除相同項, 比如: 上面的數組 其實 [-1, 0, 1], 有三組, 但是我們隻要添加1組
千萬不要用 for循環
又套一層for循環
處理這個問題, 有些認為兩層for循環求解, 可以啊, 一層尋找A, 2層尋找B, 判斷數組是否存在C = - (A + B),
思路正確, 但是這種時間復雜度很高O(n^2)
而且上手時候你會發現, 去重問題處理起來比較繁瑣
方法思路是:
數組nums 先正序排列
然後for循環
, 設置最小值下標 low = i + 1
, 最大值下標 high = nums.count - 1
最大值, 最小值 不斷收縮查找, 重復的去掉 且始終保持 low < high
(因為是正序排列 大值 >= 小值)
使得 0 – nums[i] = nums[low] + nums[high] (即: 0 = nums[low] + nums[high] + nums[i])
創建新數組 添加符合條件的 [nums[low], nums[high], nums[i]], 循環結束返回即可
接下來我們看下代碼
2、代碼
let num:[Int] = [0, 0, 0, 0, -1, 0, 1, 9, 7, 4] print("返回結果: \(self.caculate(nums: num))") func caculate(nums: [Int]) -> [[Int]] { //數組元素小於2直接返回 if nums.count < 2 { return [] } //創建空數組, 用來添加 [A,B,C] var result:[[Int]] = [] //將原數組數組正序排列, 這一步很重要, 亂序數組很難處理 let sort:[Int] = nums.sorted() //循環正序數組 for i in 0..<sort.count-1 { //創建最小值下標, 最大值下標 var low:Int = i+1 var high:Int = sort.count - 1 //A+B+C=0 定義-C 為瞭之後讓 A+B=-C let target:Int = 0 - sort[i] //如果兩個數相等直接跳過下一次循環 if i>0 && sort[i] == sort[i-1] { continue } //始終保證 最大值下標 > 最小值下標 //思路就是最大值不減小, 最小值不斷增大, 最小值不會超過最大值 //直到找到對應值, 相同值去重 while low < high { //創建sum為: 兩數字和 A+B let sum:Int = sort[low] + sort[high] //如果A+B == -C 即 A+B+C == 0 if sum == target { //數組添加新元素 result.append([sort[low], sort[high], sort[i]]) //如果當前最小值和下一位相等, 下標往前移位, 去重 while low < high && sort[low] == sort[low + 1] { low += 1 } //如果當前最大值和前一位相等, 下標往前移位, 去重 while low < high && sort[high] == sort[high - 1] { high -= 1 } //最小值向後移動一位, 最大值向前移動一位 繼續收縮, 直到跳出while low += 1 high -= 1 }else if sum < target{ //如果A+B == -C 即 A+B+C == 0 low += 1 }else { //如果A+B == -C 即 A+B+C == 0 high -= 1 } } } return result }
返回結果: [[0, 1, -1], [0, 0, 0]]
到此這篇關於IOS 算法之三數之和求解問題的文章就介紹到這瞭,更多相關IOS 算法三數之和求解內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!