Cover image for Interview Classic 150 Questions P15 3Sum

Interview Classic 150 Questions P15 3Sum

(Updated: )
algorithm
, , ,
Timeline

timeline

2025-11-11

init

two pointers

Title:

P15 3Sum

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

TLE BFS idea

Each interval splits into two intervals, the algorithm complexity is quite high.

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) { //Maximum value is still less than 0
				que.push({ i + 1, k });
			} else if (k - 1 > i + 1 && val + nums[i + 1] > 0) { //Minimum value is still greater than 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;
					}
				}
				// Both i++ and j-- should be tried
				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;
	}
};

Two pointers: fix the number of middle value

If we fix the middle number, it is difficult to remove duplicates from the middle elements, and finally we can only deduplicate uniformly. The efficiency is low.

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());
		// Fix the middle number
		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] });
					// Skip duplicate elements
					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;
	}
};

Two pointers: fix the smallest number

You can fix the smallest number. First, the smallest number must be less than 0, otherwise the sum of three numbers cannot be 0. Second, for a certain num[i] as the smallest number, if there are identical values after it, they can be skipped directly. For example, in {-2, -2, -2, …}, the selection interval of j,k for the first -2 includes the intervals of the subsequent -2s (the first interval is larger than the later intervals). Therefore, except for the first -2, the subsequent -2s are duplicate calculations.

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
#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());

		// Fix the smallest number
		for (i = 0; i < n - 2; i++) {
			j = i + 1;
			k = n - 1;
			if (i > 0 && nums[i] == nums[i - 1]) { // Skip duplicate smallest elements
				// Because the selection interval of j,k for the previous identical element includes the interval of the current identical element
				continue;
			}
			if (nums[i] > 0) { // The smallest number must be less than 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] });
					// Skip duplicate elements
					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
If a left and right that meet the requirements are found, then left++ and 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++) { // Fix the smallest number
                        if (nums[i] > 0) { // The smallest number must be less than or equal to 0
                                break;
                        }
                        if (i > 0 && nums[i] == nums[i - 1]) { // Remove duplicates
                                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;
        }
};