I just get started on Python last week and am learning by coding. Here's two piece of code that I came up with for 3sum question, both are erring in TLE(Time Limit Exceed) on my end, and I can't figure out where went wrong at present, I would love to learn from any member of the community and any suggestion to optimize is greatly appreciated.
I tried sorted/sort(), range/xrange, and they both result in TLE.
sl=sorted(nums) #0123456789 #i..l.....r for i in xrange(len(sl)-2): l=i+1 r=len(sl)-1 while(l<r): sum_=sl[i]+sl[l]+sl[r] if sum_<0: l=l+1 elif sum_>0: r=r-1 else: sublist=[sl[i],sl[l],sl[r]] if not sublist in result: result.append(sublist) l=l+1 return result for i in xrange(len(sl)): target = -sl[i] for j in xrange(i+1,len(sl)): x=sl[j] if target-x in sl[j+1:len(sl)]: if [-target,x,target-x] not in result: result.append([-target,x,target-x]) return result
@jack43 Hi there.
Your second function is brute force O(n**3). For each i, get each j and look through all the other numbers. It's probably not possible to get around TLE with that approach.
Your first solution is a better idea. The issue is with avoiding duplicate results. You look through the previous result list to check it's not a duplicate and this takes a long time.
Better would be to make results a set and sublist a tuple. This way it's O(1) to check if a result has been found already. But I just tried that and it's still too slow.
Even better is to move the pointers i, l and r past all identical numbers to avoid duplicates in the first place, rather than finding everything and checking for duplicates later. The code is a bit longer but runs much faster.
There are plenty of good solutions in the discussion forum and for what its worth mine is here ...