给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 0 <= nums.length <= 3000 -105 <= nums[i] <= 105
很显然，为了a + b + c = 0，我们可以转化成a + b = -c,即双指针的两数之和问题，当然我们也可以直接使用三个指针，本质上并无区别… 但这题关键的地方在于优化算法速度，不然随随便便就超时. 思路仍然是先排序，然后确定a的大小，将a从0遍历至length-1，在每轮遍历再通过b和c指针找出符合题意的答案。 以下为实现代码
class Solution { func threeSum(_ nums: [Int]) -> [[Int]] { if nums.count < 3 { return [] } var res = [[Int]]() // 排序 var arr = nums.sorted(by:{ return $0 < $1 }) // 将a从0遍历至末尾 for a in 0..<arr.count { // 如果a大于0并且与前一个数相同，则跳过本轮循环 if (a > 0 && arr[a] == arr[a - 1]) { continue } var b = a + 1 var c = arr.count - 1 while (b < c) { // 如果b与前面一轮循环的b相同，也跳过本轮循环。 // b要大于a+1是因为a+1是第一个b值 while (b > a + 1 && b < arr.count && arr[b] == arr[b - 1]) { b += 1 } // 如果b大于或等于c，说明本轮循环已没有不重复的组了 跳出循环 if b >= c { break } let cnt = arr[a] + arr[b] + arr[c] if cnt == 0 { let temp = [arr[a],arr[b],arr[c]] // 由于确定了a和b不同，即c肯定不同，所以不用判断res中是否已有temp res.append(temp) b += 1 } else if cnt < 0 { b += 1 } else if cnt > 0 { c -= 1 } } } return res } }
