.png)
Problem Statement:
Here you are given an integer array, you have to 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.
Note: Your solution should not have more than one element in triplets means no duplicacy
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Note: Whatever order of our solution doesn't matter and also of triplet in our ans set.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: Add-up of the triplet not equal to the zero.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: Triplet sum is equal to zero, so it's correct solution.
Constraints:
3 <= nums.length <= 3000-105 <= nums[i] <= 105
.png)
C++ Solution
class Solution{
public:
vector<vector<int>> threeSum(vector<int>& num){
sort(num.begin(),num.end());
vector<vector<int>> res;
// moves for a
for(int i=0; i<num.size()-2; i++){
if(i==0 || (i>0 && num[i]!=num[i-1])){
int lo=i+1,hi=num.size()-1,sum=0-num[i];
while(lo<hi){
if(num[lo]+num[hi]==sum){
vector<int> temp;
temp.push_back(num[i]);
temp.push_back(num[lo]);
temp.push_back(num[hi]);
res.push_back(temp);
while(lo<hi && num[lo]==num[lo+1]) lo++;
while(lo<hi && num[hi]==num[hi-1]) hi--;
lo++;
hi--;
}
else if(lo<hi && num[lo]+num[hi]<sum) lo++;
else hi--;
}
}
}
return res;
}
};
Java Solution
class Solution{
public List<List<Integer>> threeSum(int[] num){
Arrays.sort(num);
List<List<Integer>> res=new LinkedList<>();
for(int i=0; i<num.length-2; i++){
if(i==0 || (i>0 && num[i]!=num[i-1])){
int lo=i+1,hi=num.length-1,sum=0-num[i];
while(lo<hi){
if(num[lo]+num[hi]==sum){
res.add(Arrays.asList(num[i],num[lo],num[hi]));
while(lo<hi && num[lo]==num[lo+1]) lo++;
while(lo<hi && num[hi]==num[hi-1]) hi--;
lo++;
hi--;
}
else if(lo<hi && num[lo]+num[hi]<sum) lo++;
else hi--;
}
}
}
return res;
}
}
Success
Details Runtime: 206 ms, faster than 36.06% of C++ online submissions for 3Sum.
Memory Usage: 23.4 MB, less than 35.60% of C++ online submissions for 3Sum.