Day 4 Leet code series, today we will be picking the problem Three sum (https://leetcode.com/problems/3sum/).
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]]
Example 2:
Input: nums = [] Output: []
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> triplets;
int i=0;
while( i < nums.size()){
if( i == 0 || (i-1 >= 0 && nums[i-1] != nums[i])){
int first = nums[i];
int target = -first;
vector<vector<int>> pairs = twoSum(nums, i+1, nums.size()-1, target);
for(vector<int> pair: pairs){
vector<int> triplet;
triplet.push_back(first);
triplet.push_back(pair[0]);
triplet.push_back(pair[1]);
triplets.push_back(triplet);
}
}
i++;
}
return triplets;
}
vector<vector<int>> twoSum(vector<int>& nums, int start, int end, int target){
vector<vector<int>> res;
int f = start, s = end;
while(f < s){
if(f - 1 >= start && nums[f-1] == nums[f]){
f++;
continue;
}
if(s + 1 <= end && nums[s+1] == nums[s]){
s--;
continue;
}
if(nums[f] + nums[s] > target){
s--;
}
else if(nums[f] + nums[s] < target){
f++;
}
else {
vector<int> pair;
pair.push_back(nums[f]);
pair.push_back(nums[s]);
res.push_back(pair);
f++;
}
}
return res;
}
};
Explaination:
- We will be using 2 sum method to solve this problem.
- We will be finding the target value for every number in the array (except the values that are repeating).
- Suppose the number is -4 then we will be looking for 4 and so, we will be finding a 2sum for 4.
- Then we will be adding that in the pair and then return the vector<vector<int>.
ADDITIONAL KNOWLEDGE 
Leave a comment