Straight forward Python AC O(n^2) solution with decent explanation


  • 15
    I
    class Solution:
        # @param {integer[]} nums
        # @return {integer[][]}
        def threeSum(self, nums):
            if len(nums) <3: # deal with special input
                return []
            elif len(nums) == 3:
                if sum(nums) == 0:
                    return [sorted(nums)]
    
    
            nums = sorted(nums) # sorted, O(nlgn)
            ans = []
    
            for i in range(len(nums) -2):
                j = i+1
                k = len(nums) -1 # hence i < j < k
    
                while j<k: # if not cross line
                    temp_sum = nums[i] + nums[j] + nums[k]
                    if temp_sum == 0:
                        ans.append((nums[i], nums[j], nums[k]))
    
                    if temp_sum > 0: # which means we need smaller sum, move k backward, remember we sort the array
                        k -= 1
                    else:
                        j += 1
    
            return list(set(tuple(ans))) # I bet this is not the best way to eliminate duplicate solutions

  • 5

    Thank you so much!
    I've been trying to solve the simplification problem with methods like list(set(ans)), which makes error. Now I get it!

    ------updated-----
    well,I found a quicker way to avoid duplication:

    def threeSum(self, nums):
        if len(nums) <3: 
            return []
        elif len(nums) == 3:
            if sum(nums) == 0:
                return [sorted(nums)]
        nums.sort()
        res = []
        for i in list(range(len(nums)-2)):
            if i > 0 and nums[i] == nums[i-1]: # avoid duplication
                continue
            j = i + 1
            k = len(nums) - 1
            while j < k:
                if j > i + 1 and nums[j] == nums[j-1]: # avoid duplication
                    j += 1
                    continue
                if k < len(nums) - 1 and nums[k] == nums[k+1]: # avoid duplication
                    k -= 1
                    continue
                if nums[i] + nums[j] + nums[k] == 0:
                    res.append([nums[i],nums[j],nums[k]])
                if nums[i] + nums[j] + nums[k] < 0:
                    j += 1
                else:
                    k -= 1
        return res
    

    This makes a 232ms answer


  • 0
    G

    why do you need list in
    for i in list(range(len(nums)-2)): ?


  • 3
    Z

    @carterbao

    slightly simpler and faster solution 170 ms

    One possible optimization is to check this, then break earlier.

    if nums[i] + nums[j] + nums[j + 1] > 0:
        return res
    
    class Solution(object):
        def threeSum(self, nums):
            nums.sort()
            res = []
            for i in range(len(nums) - 2):
                j = i + 1
                # small optimization
                if nums[i] + nums[j] + nums[j + 1] > 0:
                    return res
                k = len(nums) - 1
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                while j < k:
                    if j > i + 1 and nums[j] == nums[j - 1]:
                        j += 1
                        continue
                    total = nums[i] + nums[j] + nums[k]
                    if total > 0:
                        k -= 1
                    else:
                        if total == 0:
                            res.append([nums[i], nums[j], nums[k]])
                        j += 1
            return res
    

  • 2
    K

    Time limit exceeded.


  • 0
    A

    @carterbao
    why do you use if...if.. else rather than if...elif...else? is the former more efficient?
    I just a begginer and do a little change on your code using the latter again but time limit exceeded.0_1498098587681_微信截图_20170622102726.png


  • 0
    B

    if you encountered time limit error, you can add below code to the beginning of the loop of i

                if i != 0 and nums[i]==nums[i-1]:
                    continue
    
    

  • 0
    J

    A generalization solution using 2Sum idea,

    def three_sum(nums):
        nums.sort()
        solution = []
        for idx,tgt in enumerate(nums):
            if idx>0 and nums[idx] == nums[idx-1]:
                continue
            path = {}
            vist = set()
            for i in xrange(idx+1,len(nums)):
                if nums[i] not in path:
                    path[-tgt-nums[i]] = nums[i]
                elif nums[i] in path and nums[i] not in vist:
                    solution.append([tgt,path[nums[i]],nums[i]])
                    vist.add(nums[i])
        return solution
    

  • 0
    S

    @jianx
    This is brilliant. So elegant. Could you explain the logic that brought you to use the dict and set to track? The -tgt - nums[i] bit has me thrown.

    How does nums[i]'s presence as a key in path and non-presence as a set value in vist determine that this iteration's sum == 0?


  • 0
    J

    @stueygk The dictionary is used for 2Sum where its key is the target value and value is current value. Once it finds the target value, you are done.

    The vist set is to avoid duplicates. Examples like [-4, -1, -1, 0, 1, 2], the second -1 wouldn't show up in the answer once it has been visited and already is an answer.


Log in to reply
 

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