Key ideas:

  1. Sort the nums first.
  2. Then, we travel the nums, pick current element as nums[i], and apply LeetCode101: 167. Two Sum II - Input Array Is Sorted to the remains.
  3. We skip the same numbers to avoid duplicate.
class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int l, r, sum, T;
		vector<vector<int>> res;
		for (int i = 0; i < nums.size(); i++) {
			// Skip same numbers to avoid duplicate
			if(i > 0 && nums[i] == nums[i-1]) {
				continue;
			}

			l = i + 1;
			r = nums.size() - 1;
			T = 0 - nums[i];
			while (l < r) {
				sum = nums[l] + nums[r];
				if (sum == T) {
					res.push_back({nums[i], nums[l], nums[r]});

					// Skip same numbers in each side to avoid duplicate
					while (l < r && nums[l] == nums[l + 1])
						l++;
					while (l < r && nums[r] == nums[r - 1])
						r--;
					l++;
					r--;
				} else if (sum < T) {
					l++;
				} else {
					r--;
				}
			}
		}
		return res;
	}
};