Python easy to understand solution (O(n*n) time).


  • 53
    C
    def threeSum(self, nums):
        res = []
        nums.sort()
        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:
                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[r-1]:
                        r -= 1
                    l += 1; r -= 1
        return res

  • 2

  • 5
    C

    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.


  • 2
    Z

    I totally agree with you.


  • 2
    M

    Can you explain me why you added this condition: if i > 0 and nums[i] == nums[i-1]


  • 0
    C

    This is a way to remove duplicates, for example, if the list is [1, 1, 1, 3], and the sum is 5, you will only get one [1, 1, 3] as the answer.


  • 1
    M

    oh, thank you very much


  • 1
    N

    if nums[i] > 0:
    break


  • 0
    W

    I took about half an hour to understand... Still, I think it would be better if you add explanation near your code...


  • 5
    J

    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.


  • 0
    B

    @napoleonwxu if nums[i] >= 0:break


  • 0
    B

    @banxi said in Python easy to understand solution (O(n*n) time).:

    @napoleonwxu if nums[i] >= 0:break

    sorry >= may cause bug.


  • 1
    K

    Excuse me, but running this code returns ' time limit exceeded' for me.

    Is there anybody the same with my situation?


  • 0
    W

    @kghch

    Yes encountered the same situation.

    @administrators That's really interesting


  • 0

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


  • 0
    W

    @1337c0d3r

    '''

     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
    

    '''


  • 1

    @whglamrock No, your code is not the same as @caikehe 's.

    Optimization #1:

    These two while loops could be put inside the if 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:
    

  • 0
    W

    @1337c0d3r

    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.


  • 0
    L

    @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.


  • 0
    W

    @mamoru because the answer should be unique


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.