15. 3Sum

题目

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题目大意

给定一个数组，要求在这个数组中找出 3 个数之和为 0 的所有组合。

解题思路

用 map 提前计算好任意 2 个数字之和，保存起来，可以将时间复杂度降到 O(n^2)。这一题比较麻烦的一点在于，最后输出解的时候，要求输出不重复的解。数组中同一个数字可能出现多次，同一个数字也可能使用多次，但是最后输出解的时候，不能重复。例如 [-1，-1，2] 和 [2, -1, -1]、[-1, 2, -1] 这 3 个解是重复的，即使 -1 可能出现 100 次，每次使用的 -1 的数组下标都是不同的。

这里就需要去重和排序了。map 记录每个数字出现的次数，然后对 map 的 key 数组进行排序，最后在这个排序以后的数组里面扫，找到另外 2 个数字能和自己组成 0 的组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if (nums.size() < 3) return result;
        
        // 统计每个数字出现的次数
        map<int, int> count_map;
        for (int num : nums) {
            count_map[num]++;
        }
        
        // 提取不重复的数字并排序
        vector<int> unique_nums;
        for (auto& pair : count_map) {
            unique_nums.push_back(pair.first);
        }
        sort(unique_nums.begin(), unique_nums.end());
        
        int n = unique_nums.size();
        
        // 遍历所有可能的第一个数a
        for (int i = 0; i < n; ++i) {
            int a = unique_nums[i];
            count_map[a]--;  // 已使用一个a
            
            // 遍历可能的第二个数b（b >= a，避免重复）
            for (int j = i; j < n; ++j) {
                int b = unique_nums[j];
                // 确保有足够的b可以使用
                if (count_map[b] == 0) continue;
                count_map[b]--;  // 已使用一个b
                
                int c = -a - b;  // 计算需要的第三个数
                // 确保c存在且c >= b（避免重复）
                if (count_map.find(c) != count_map.end() && count_map[c] > 0 && c >= b) {
                    result.push_back({a, b, c});
                }
                
                count_map[b]++;  // 恢复b的计数
            }
            
            count_map[a]++;  // 恢复a的计数
        }
        
        return result;
    }
};

代码解析

  1. 哈希表计数：
    • 使用count_map记录每个数字出现的次数，便于快速查询和控制使用次数
    • 例如对于nums = [-1, -1, 2]，count_map会记录为{-1:2, 2:1}
  2. 去重机制：
    • 通过unique_nums数组确保只处理不重复的数字
    • 遍历顺序保证a ≤ b ≤ c，避免同一组合的不同排列被视为不同解
    • 每次使用数字后暂时减少计数，使用完毕后恢复，确保正确处理重复数字
  3. 寻找第三个数：
    • 对于每个a和b，计算c = -a - b
    • 检查c是否存在、是否有剩余可用次数，以及是否满足c ≥ b