时间轴

2025-11-11

init

题目：

P15 三数之和

https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150

TLE BFS 思想

每个区间分裂成两个区间，算法复杂度相当高。

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
54
55
56
57
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>

using std::vector;
using std::queue;
using std::pair;

class Solution {
    public:
	vector<vector<int> > threeSum(vector<int> &nums)
	{
		// nums[i] + nums[j] + nums[k] == 0

		std::sort(nums.begin(), nums.end());

		vector<vector<int> > res;

		int n = nums.size();
		int i, j, k, val;

		queue<pair<int, int> > que;

		que.push({ 0, n - 1 });
		while (!que.empty()) {
			i = que.front().first;
			k = que.front().second;

			val = nums[i] + nums[k];
			que.pop();

			if (i + 1 < k - 1 && val + nums[k - 1] < 0) { //最大值还小于0
				que.push({ i + 1, k });
			} else if (k - 1 > i + 1 && val + nums[i + 1] > 0) { //最小值还大于0
				que.push({ i, k - 1 });
			} else {
				for (j = i + 1; j < k; j++) {
					if (val + nums[j] == 0) {
						res.push_back({ nums[i], nums[j], nums[k] });
						break;
					}
				}
				// i++或j--都要尝试
				if (i + 1 < k + 1) {
					que.push({ i + 1, k });
				}
				if (k - 1 > i + 1) {
					que.push({ i, k - 1 });
				}
			}
		}
		std::sort(res.begin(), res.end());
		res.erase(std::unique(res.begin(), res.end()), res.end());
		return res;
	}
};

双指针 固定中间大小的那个数

如果我们固定中间那个数，那么中间元素很难去除重复，最后只能统一去重。效率偏低。

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
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	vector<vector<int> > threeSum(vector<int> &nums)
	{
		int n = nums.size();
		int i, j, k;
		int left_val, right_val;
		vector<vector<int> > res;
		std::sort(nums.begin(), nums.end());
		// 固定中间那个数
		for (j = 1; j < n - 1; j++) {
			i = j - 1;
			k = j + 1;
			while (i >= 0 && k < n) {
				if (nums[i] + nums[k] + nums[j] > 0) {
					i--;
				} else if (nums[i] + nums[k] + nums[j] < 0) {
					k++;
				} else {
					res.push_back({ nums[i], nums[j], nums[k] });
					// 跳过重复元素
					left_val = nums[i];
					right_val = nums[k];
					while (i >= 0 && nums[i] == left_val) {
						i--;
					}
					while (k < n && nums[k] == right_val) {
						k++;
					}
				}
			}
		}
		std::sort(res.begin(), res.end());
		res.erase(std::unique(res.begin(), res.end()), res.end());

		return res;
	}
};

双指针 固定最小的那个数

可以固定最小的那个数。首先最小的数一定是小于 0 的，否则三数之和不可能为 0。其次，对于某一个 num[i]，作为最小的数，如果后面有和它相同的值，可以直接跳过。因为譬如{-2, -2, -2, …}第一个-2 的 j,k 选择区间是包含后面的-2 的区间的（第一个区间大于后面的区间）。因此除了第一个-2，后面-2 的都是重复计算。

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
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	vector<vector<int> > threeSum(vector<int> &nums)
	{
		int n = nums.size();
		int i, j, k;
		int left_val, right_val;
		vector<vector<int> > res;
		std::sort(nums.begin(), nums.end());
		// 固定最小的那个数
		for (i = 0; i < n - 2; i++) {
			j = i + 1;
			k = n - 1;
			if (i > 0 && nums[i] == nums[i - 1]) { // 跳过重复的最小元素
				// 因为前一个相同元素的j,k选择区间包含了当前相同元素的这个区间
				continue;
			}
			if (nums[i] > 0) { // 最小的数必定小于0
				continue;
			}
			while (j < k) {
				if (nums[i] + nums[k] + nums[j] > 0) {
					k--;
				} else if (nums[i] + nums[k] + nums[j] < 0) {
					j++;
				} else {
					res.push_back({ nums[i], nums[j], nums[k] });
					// 跳过重复元素
					left_val = nums[j];
					right_val = nums[k];
					while (j < k && nums[j] == left_val) {
						j++;
					}
					while (k < j && nums[k] == right_val) {
						k--;
					}
				}
			}
		}
		return res;
	}
};

hot100 rewrite
如果找到了一个 left 和 right 符合要求，那么 left++且 right–；

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
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &nums)
        {
                int n = nums.size();
                int i, left, right;
                std::sort(nums.begin(), nums.end());
                vector<vector<int> > ret;
                for (i = 0; i < n - 2; i++) { // 固定最小的那个数
                        if (nums[i] > 0) { // 最小的那个数肯定小于等于0
                                break;
                        }
                        if (i > 0 && nums[i] == nums[i - 1]) { // 去除重复
                                continue;
                        }

                        left = i + 1;
                        right = n - 1;
                        while (left < right) {
                                if (nums[left] + nums[right] < -nums[i]) {
                                        left++;

                                } else if (nums[left] + nums[right] > -nums[i]) {
                                        right--;

                                } else {
                                        ret.push_back({ nums[left], nums[right], nums[i] });
                                        while(left < right && nums[left] == ret.back()[0]){
                                                left++;
                                        }
                                        while(right > left && nums[right] == ret.back()[1]){
                                                right--;
                                        }

                                }
                        }
                }
                return ret;
        }
};