# Leetcode 15 Solution

https://leetcode.com/problems/3sum

## Thinking Process

First of all, it’s very unlikely that we can finish this question within `O(N)` time, because we can’t even do that for the two-sum question. If our target time complexity is `O(N^2)`, it means we can we whatever we want (within `O(N^2)` time) to simplify the question without increasing the overall time complexity.

That being said, let’s sort the array before we even try to tackle it.

Now the question is to find three numbers in a sorted array that add up to the target. If we fix the first number, we just need to find two numbers in a sorted array, which is even simpler. This is exactly the same question as two-sum-ii-input-array-is-sorted.

So we just have to iterate the first number, and then call the algorithm to address two-sum-ii-input-array-is-sorted.

See, by transforming the question, we completely converted this question to simpler ones, so that no complicated algorithm design is needed here.

## Time & Space Complexity

Assuming `N` is the size of the array

• Time complexity: `O(N^2)`
• Space complexity: `O(N)`

## Solution

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());

for (int i = 0; i < nums.size(); i++)
{
if (i > 0 && nums[i] == nums[i - 1])
continue;

int target = -nums[i];

int l = i + 1;
int r = nums.size() - 1;

while (l < r)
{
if (nums[l] + nums[r] < target)
l++;
else if (nums[l] + nums[r] > target)
r--;
else
{
vector<int> a;
a.push_back(nums[i]);
a.push_back(nums[l]);
a.push_back(nums[r]);

res.push_back(a);

do
{
l++;
} while (nums[l] == nums[l - 1] && l < nums.size());

do
{
r--;
} while (nums[r] == nums[r + 1] && r >= 0);
}
}
}

return res;
}
};
``````