This is my submission for 3Sum Problem on Leetcode and the complexity comes out to be O(n^2), since I have used a nested for loop for the length of the nums array (nums.length()<=3000). However, I am getting TLE on all zeros case. Can anyone help me understand what is wrong with my complexity? The code file with the testcase is attached.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
set<vector<int>> ans;
vector<int> present(200001,0);
int n = nums.size();
for(int x=0;x<n;x++)
{
int val = nums[x];
int ind = val + 100000;
present[ind]++;
}
for(int x=0;x<n;x++)
{
int v1 = nums[x];
present[v1+100000]--;
for(int y=0;y<n ;y++)
{
if(y==x)
{
continue;
}
int v2 = nums[y];
present[v2+100000]--;
int rem = -v1-v2;
if(rem>=-100000 && rem<=100000 && present[rem+100000]>0)
{
vector<int> pans;
pans.push_back(v1);
pans.push_back(v2);
pans.push_back(rem);
sort(pans.begin(),pans.end());
if(v1+v2+rem==0)
{
// cout<<"inserting : {"<<v1<<" "<<v2<<" "<<rem<<"}"<<endl;
ans.insert(pans);
}
}
present[v2+100000]++;
}
present[v1+100000]++;
}
vector<vector<int>> ret;
for(auto i : ans)
{
ret.push_back(i);
}
return ret;
}
};
