forked from wahyuhjr/OpenEmailGenerator
-
Notifications
You must be signed in to change notification settings - Fork 1
/
3SUM_leetcode.cpp
32 lines (31 loc) · 1.59 KB
/
3SUM_leetcode.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin() , nums.end()); //Sorted Array
if(nums.size() < 3){ // Base Case 1
return {};
}
if(nums[0] > 0){ // Base Case 2
return {};
}
unordered_map<int , int> hashMap;
for(int i = 0 ; i < nums.size() ; ++i){ //Hashing of Indices
hashMap[nums[i]] = i;
}
vector<vector<int>> answer;
for(int i = 0 ; i < nums.size() - 2 ; ++i){ //Traversing the array to fix the number.
if(nums[i] > 0){ //If number fixed is +ve, stop there because we can't make it zero by searching after it.
break;
}
for(int j = i + 1 ; j < nums.size() - 1 ; ++j){ //Fixing another number after first number
int required = -1*(nums[i] + nums[j]); //To make sum 0, we would require the -ve sum of both fixed numbers.
if(hashMap.count(required) && hashMap.find(required)->second > j){ //If it exists in hashmap and its last occurrence index > 2nd fixed index, we found our triplet.
answer.push_back({nums[i] , nums[j] , required});
}
j = hashMap.find(nums[j])->second; //Update j to last occurence of 2nd fixed number to avoid duplicate triplets.
}
i = hashMap.find(nums[i])->second; //Update i to last occurence of 1st fixed number to avoid duplicate triplets.
}
return answer; //Return answer vector.
}
};