IOS如何實(shí)現(xiàn)三數(shù)之和

小編給大家分享一下IOS如何實(shí)現(xiàn)三數(shù)之和，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

1、三數(shù)求和簡單介紹

對于一個整數(shù)的數(shù)組, 是否存在a, b, c 使得 a + b + c = 0, 返回a b c 數(shù)組，相同數(shù)組只返回一個,:

例如:

[-1, -2, 6, 5, 0, 1, 2, -1, -1] 返回 [[-1, 0, 1], [-2, 0, 2], [-1, -1, 2]]

關(guān)鍵點(diǎn)：

① 找到和為0的三個數(shù)

② 去除相同項(xiàng), 比如: 上面的數(shù)組 其實(shí) [-1, 0, 1], 有三組, 但是我們只要添加1組

千萬不要用 for循環(huán)又套一層for循環(huán) 處理這個問題, 有些認(rèn)為兩層for循環(huán)求解, 可以啊, 一層尋找A, 2層尋找B, 判斷數(shù)組是否存在C = - (A + B), 思路正確, 但是這種時間復(fù)雜度很高O(n^2) 而且上手時候你會發(fā)現(xiàn), 去重問題處理起來比較繁瑣

方法思路是：

數(shù)組nums 先正序排列

然后for循環(huán), 設(shè)置最小值下標(biāo) low = i + 1, 最大值下標(biāo) high = nums.count - 1

最大值, 最小值 不斷收縮查找, 重復(fù)的去掉 且始終保持 low < high (因?yàn)槭钦蚺帕?大值 >= 小值)

使得 0 - nums[i] = nums[low] + nums[high] (即: 0 = nums[low] + nums[high] + nums[i])

創(chuàng)建新數(shù)組 添加符合條件的 [nums[low], nums[high], nums[i]], 循環(huán)結(jié)束返回即可

接下來我們看下代碼

2、代碼

let num:[Int] = [0, 0, 0, 0, -1, 0, 1, 9, 7, 4]
print("返回結(jié)果: \(self.caculate(nums: num))")
   
    func caculate(nums: [Int]) -> [[Int]]  {
        
        //數(shù)組元素小于2直接返回
        if nums.count < 2 {
            return []
        }
        //創(chuàng)建空數(shù)組, 用來添加 [A,B,C]
        var result:[[Int]] = []
        //將原數(shù)組數(shù)組正序排列, 這一步很重要, 亂序數(shù)組很難處理
        let sort:[Int] = nums.sorted()
        
        //循環(huán)正序數(shù)組
        for i in 0..<sort.count-1 {
            
            //創(chuàng)建最小值下標(biāo), 最大值下標(biāo)
            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]
            
            //如果兩個數(shù)相等直接跳過下一次循環(huán)
            if i>0 && sort[i] == sort[i-1] {
                continue
            }
            
            //始終保證 最大值下標(biāo) > 最小值下標(biāo)
            //思路就是最大值不減小, 最小值不斷增大, 最小值不會超過最大值
            //直到找到對應(yīng)值, 相同值去重

 
            while low < high {
                //創(chuàng)建sum為: 兩數(shù)字和 A+B
                let sum:Int = sort[low] + sort[high]
                
                //如果A+B == -C 即 A+B+C == 0
                if sum == target {
                    //數(shù)組添加新元素
                    result.append([sort[low], sort[high], sort[i]])
                    //如果當(dāng)前最小值和下一位相等, 下標(biāo)往前移位, 去重
                    while low < high && sort[low] == sort[low + 1] {
                        low += 1
                    }
                    //如果當(dāng)前最大值和前一位相等, 下標(biāo)往前移位, 去重
                    while low < high && sort[high] == sort[high - 1] {
                        high -= 1
                    }
                    //最小值向后移動一位, 最大值向前移動一位 繼續(xù)收縮, 直到跳出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
        
    }

返回結(jié)果: [[0, 1, -1], [0, 0, 0]]

以上是“IOS如何實(shí)現(xiàn)三數(shù)之和”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道！