Swift刷算法：三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一、转为2数之和 + Hash表查找

class Solution {
   func threeSum(_ nums: [Int]) -> [[Int]] {
       // 存放符合a+b+c=0的结果
       var res: [Int : [Int]] = [:]
       // 备忘录
       var memo: Set<Int> = []

       for i in 0 ..< nums.count {
           // nums[i]是三元组第1个值
           // 用目标值0减去nums[i]得到新的目标值target，将问题转为两数之和
           let target = 0 - nums[i]

           // target变化，清空备忘录
           memo.removeAll()

           // 注意j是从j+1开始的
           for j in i+1 ..< nums.count {
               // nums[j]是三元组第2个值
               // dst是三元组第3个值
               let dst = target - nums[j]

               // 用集合Set查找是否存在dst，复杂度是O(1)
               if memo.contains(dst) {
                   // 计算结果的hash值作为key，是判断重复的关键
                   let key = nums[i].hashValue ^ nums[j].hashValue ^ dst.hashValue
                   // 三元组结果尚未存在则加入结果字典
                   if res[key] == nil {
                       res[key] = [nums[i], nums[j], dst]
                   }
               } else {
                   // 把当前值加入备忘录
                   memo.insert(nums[j])
               }
           }
       }
       // 只需返回[[Int]]结果
       return Array(res.values)
   }
}

方法二、排序 + 双指针

class Solution {
    func threeSum(_ nums: [Int]) -> [[Int]] {
        // 从小到大排序
        let nums = nums.sorted()
        // 数组个数须>=3，且最小值不能>0
        guard nums.count >= 3, nums[0] <= 0 else { 
            return [] 
        }
        // 最终结果
        var res: [[Int]] = []

        var pre = 0
        while pre < nums.count - 2 {
            let target = 0 - nums[pre]
            var left = pre + 1
            var right = nums.count - 1
            
            while left < right {
                let sum = nums[left] + nums[right]

                if sum == target {
                    // 符合三数之和为0，加入结果
                    res.append([nums[pre], nums[left], nums[right]])
                    left += 1
                    right -= 1

                    // 排除第2个值重复
                    while left < right, nums[left] == nums[left - 1] {
                        left += 1
                    }
                    // 排除第3个值重复
                    while left < right, nums[right] == nums[right + 1] {
                        right -= 1
                    }
                } else if sum < target {
                    left += 1
                } else {
                    right -= 1
                }
            }
            pre += 1

            // 排除第1个值重复
            while pre < nums.count - 1, nums[pre] == nums[pre - 1] {
                pre += 1
            }
        }
        
        return res
    }
}

image.png