def threeSum(self, nums):
res = []
nums.sort()
for i in xrange(len(nums)2):
if i > 0 and nums[i] == nums[i1]:
continue
l, r = i+1, len(nums)1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l +=1
elif s > 0:
r = 1
else:
res.append((nums[i], nums[l], nums[r]))
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r1]:
r = 1
l += 1; r = 1
return res
Python easy to understand solution (O(n*n) time).


Your code is basically the same as:
https://github.com/shichaoan/leetcodepython/commit/2edda1c4ad5dae9edace5fb6615ad49a9b051f0f

Yes, after you practice a period of time in LeetCode, you can summarize some tips about how to tackle a category of problems. Just like 3sum and 4sum, after you checking the discussion in leetcode, you can get the idea about how to remove duplicates. The process more or less is the same indeed. There are always some smart leetcoders devise out smart solutions.

The way to think about it is since it's 3 sum, there's only going to be 3 numbers. So to find the combinations of 3 numbers, he is iterating through the list with the first pointer, and then trying to find two extra numbers to sum to 0. Since the list is ordered, the right pointer will always be higher than the middle pointer. So if the sum is too large, you can move the right pointer back one. On the other hand, if the sum is too small (below 0), then move the middle pointer up one.


@banxi said in Python easy to understand solution (O(n*n) time).:
@napoleonwxu if nums[i] >= 0:break
sorry
>=
may cause bug.


@whglamrock I added a test case yesterday so that's why it caused Python to TLE. I have fixed this. Sorry about that.

'''
def threeSum(self, nums): if (not nums) or len(nums) < 3: return [] nums.sort() ans = [] for i in xrange(len(nums)  2): if i > 0 and nums[i] == nums[i  1]: continue l, r = i + 1, len(nums)  1 while l < r: if i + 1 < l < len(nums)  1 and nums[l] == nums[l  1]: l += 1 continue if len(nums)  1 > r > i + 1 and nums[r] == nums[r + 1]: r = 1 continue if nums[i] + nums[l] + nums[r] == 0: ans.append([nums[i], nums[l], nums[r]]) l += 1 r = 1 elif nums[i] + nums[l] + nums[r] < 0: l += 1 else: r = 1 return ans
'''
This is mine. I don't see much difference here but mine still got TLE.
I tried modifying my version to be similar to caikehe's, but doesn't do any good. Still TLE.
'''
def threeSum(self, nums): if not nums or len(nums) < 3: return [] nums.sort() ans = [] for i in xrange(len(nums)  2): if i > 0 and nums[i] == nums[i  1]: continue l, r = i + 1, len(nums)  1 while l < r: while i + 1 < l < len(nums)  1 and nums[l] == nums[l  1]: l += 1 while i + 1 < r < len(nums)  1 and nums[r] == nums[r + 1]: r = 1 if l >= r: break if nums[i] + nums[l] + nums[r] == 0: ans.append([nums[i], nums[l], nums[r]]) l += 1 r = 1 elif nums[i] + nums[l] + nums[r] < 0: l += 1 else: r = 1 return ans
'''

@whglamrock No, your code is not the same as @caikehe 's.
Optimization #1:
These two
while
loops could be put inside theif nums[i] + nums[l] + nums[r] == 0
condition (3129ms to 1672ms):while i + 1 < l < len(nums)  1 and nums[l] == nums[l  1]: l += 1 while i + 1 < r < len(nums)  1 and nums[r] == nums[r + 1]: r = 1
Optimization #2:
Remove repeating calculation of
nums[i] + nums[l] + nums[r]
by caching it in a variable, it is repeated twice in a while loop which is significant (1672ms to 1288ms):if nums[i] + nums[l] + nums[r] == 0: ... elif nums[i] + nums[l] + nums[r] < 0:
to
s = nums[i] + nums[l] + nums[r] if s == 0: ... elif s < 0:

I tried the second one and it makes some sense to me.
In terms of the first one? I just see it as different way of programming. Either way SHOULD be okay. And definitely in real interview both way will work.
I understand the difference you mentioned and I think OJ is not supposed to just accept one specific version. Because what really matters here is the time/space complexity.

@whglamrock I met the same problem. O(n^2) time complexity but significantly slower than other submissions. Time cost results generated by the LeetCode server are sometimes unstable. Once after I had ACed a question I tried to improve my code, and when I submited the new version of the code it's slower than the first one. I checked the code and didn't find any problem and submited the second version of the code again. This time it's faster than the first 2 submissions.
In this question, originally I calculated the sum in a repeating manner just like you, and I got AC. Then I tried to "optimize" my code by storing the sum in a variable, and I got TLE.
So I agree what matters here is time/space complexity. I admit in some cases improvement at constant level is important, but it's not suitable for most users of LeetCode when they are trying to learn algorithm or programming language(especially python) in this website.
