任意一个三元组的和都为 0。如果我们直接使用三重循环枚举三元组，会得到 O(N^3) 个满足题目要求的三元组（其中 N 是数组的长度）时间复杂度至少为 O(N^3)。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高，因此我们要换一种思路来考虑这个问题。
「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
也就是说，我们枚举的三元组 (a, b, c) 满足 a \leq b \leq c，保证了只有 (a, b, c) 这个顺序会被枚举到，而 (b, a, c)、(c, b, a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。
nums.sort() for first = 0 .. n-1 // 只有和上一次枚举的元素不相同，我们才会进行枚举 if first == 0 or nums[first] != nums[first-1] then for second = first+1 .. n-1 if second == first+1 or nums[second] != nums[second-1] then for third = second+1 .. n-1 if third == second+1 or nums[third] != nums[third-1] then // 判断是否有 a+b+c==0 check(first, second, third)
这种方法的时间复杂度仍然为 O(N^3)，毕竟我们还是没有跳出三重循环的大框架。然而它是很容易继续优化的，可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b’ 时，由于 b’ > b，那么满足 a+b’+c’=0 的 c’ 一定有 c’ < c，即 c’ 在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。
nums.sort() for first = 0 .. n-1 if first == 0 or nums[first] != nums[first-1] then // 第三重循环对应的指针 third = n-1 for second = first+1 .. n-1 if second == first+1 or nums[second] != nums[second-1] then // 向左移动指针，直到 a+b+c 不大于 0 while nums[first]+nums[second]+nums[third] > 0 third = third-1 // 判断是否有 a+b+c==0 check(first, second, third)
classSolution: defthreeSum(self, nums: List[int]) -> List[List[int]]: n = len(nums) nums.sort() ans = list() # 枚举 a for first inrange(n): # 需要和上一次枚举的数不相同 if first > 0and nums[first] == nums[first - 1]: continue # c 对应的指针初始指向数组的最右端 third = n - 1 target = -nums[first] # 枚举 b for second inrange(first + 1, n): # 需要和上一次枚举的数不相同 if second > first + 1and nums[second] == nums[second - 1]: continue # 需要保证 b 的指针在 c 的指针的左侧 while second < third and nums[second] + nums[third] > target: third -= 1 # 如果指针重合，随着 b 后续的增加 # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if second == third: break if nums[second] + nums[third] == target: ans.append([nums[first], nums[second], nums[third]]) return ans
functhreeSum(nums []int) [][]int { n := len(nums) sort.Ints(nums) ans := make([][]int, 0) // 枚举 a for first := 0; first < n; first++ { // 需要和上一次枚举的数不相同 if first > 0 && nums[first] == nums[first - 1] { continue } // c 对应的指针初始指向数组的最右端 third := n - 1 target := -1 * nums[first] // 枚举 b for second := first + 1; second < n; second++ { // 需要和上一次枚举的数不相同 if second > first + 1 && nums[second] == nums[second - 1] { continue } // 需要保证 b 的指针在 c 的指针的左侧 for second < third && nums[second] + nums[third] > target { third-- } // 如果指针重合，随着 b 后续的增加 // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环 if second == third { break } if nums[second] + nums[third] == target { ans = append(ans, []int{nums[first], nums[second], nums[third]}) } } } return ans }
