Classic Interview 150 Questions P15 3Sum

---

Timeline

Timeline

2025-11-11

init

Two pointers

---

Problem:

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, making the algorithm complexity quite high.

#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) { //The maximum value is still less than 0.
				que.push({ i + 1, k });
			} else if (k - 1 > i + 1 && val + nums[i + 1] > 0) { //The 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-- must 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 middle-sized number.

If we fix the middle number, it is difficult to deduplicate the middle element, and we can only deduplicate at the end. Efficiency is low.

#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.

We 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 given num[i] as the smallest number, if there are identical values after it, we can skip them directly. For example, in {-2, -2, -2, …}, the j,k selection interval for the first -2 contains the interval for the later -2s (the first interval is larger than the later intervals). Therefore, except for the first -2, all subsequent -2s are duplicate calculations.

#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 j,k selection interval of the previous identical element contains 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–;

#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;
        }
};