#### Link to the Problem

#### Thought Process

As we have already solved “Two Sum” problem already, let’s reuse our existing knowledge to solve this problem. We know the `target`

and we want to search 3 numbers. We know how to search 2 numbers, so if we fix one number at a time and look for the other two numbers using our previous solution that would solve this problem as well. Say the target is `N`

and we want to find numbers `a`

, `b`

, `c`

. We will fix each number as `a`

one by one and all we have to search for is two numbers `b`

and `c`

with the target sum `N-a`

. This is precisely our “Two Sum” problem.

#### Video Explanation

#### Code

/* Watch video explanation here: https://youtu.be/MmhfOzYMYPk */ | |

class Solution { | |

vector<vector<int>> ans; // Stores the final answer. | |

/* Skip the duplicates. */ | |

int increment(vector<int>& nums, int cur) { | |

int n = nums.size(); | |

int j=cur+1; | |

while (j < n && nums[j] == nums[cur]) { | |

j++; | |

} | |

return j; | |

} | |

/* Skip the duplicates. */ | |

int decrement(vector<int>& nums, int cur) { | |

int j=cur-1; | |

while (j >= 0 && nums[j] == nums[cur]) { | |

j--; | |

} | |

return j; | |

} | |

/* Pairs of numbers in array `nums` from index `start` to | |

* index `end` with sum `target`. | |

*/ | |

void twoSum(vector<int>& nums, int start, | |

int end, int target, int a) { | |

while (start < end) { | |

if (nums[start]+nums[end] == target) { | |

// Add the triple in the answer. | |

ans.push_back({nums[start], nums[end], a}); | |

start = increment(nums, start); | |

end = decrement(nums, end); | |

} else if (nums[start]+nums[end] < target) { | |

start = increment(nums, start); | |

} else { | |

end = decrement(nums, end); | |

} | |

} | |

} | |

public: | |

vector<vector<int>> threeSum(vector<int>& nums) { // Time: O(n^2) | |

sort(nums.begin(), nums.end()); // O(nlogn) | |

int n = nums.size(); | |

for (int i=0; i<n; i=increment(nums, i)) { // n * | |

int a = nums[i]; | |

twoSum(nums, i+1, n-1, -a, a); // O(n) | |

} | |

return ans; | |

} // Space: O(1) | |

}; |

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added. I have created a Youtube Channel for quicker explanation, so subscribe to the channel too.

Happy Coding!