### Leetcode 15. 3Sum

3Sum

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

#### Code

 /* Watch video explanation here: https://youtu.be/MmhfOzYMYPk */ class Solution { vector> ans; // Stores the final answer. /* Skip the duplicates. */ int increment(vector& 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& 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& 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> threeSum(vector& nums) { // Time: O(n^2) sort(nums.begin(), nums.end()); // O(nlogn) int n = nums.size(); for (int i=0; i
view raw Leetcode_15.cpp hosted with ❤ by GitHub

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!