Share my python code, run time 200+- 20ms


  • 11
    L
    class Solution:
        # @return a list of lists of length 4, [[val1,val2,val3,val4]]
        def fourSum(self, num, target):
            num.sort()
            result = []
            for i in xrange(len(num)-3):
                if num[i] > target/4.0:
                    break
                if i > 0 and num[i] == num[i-1]:
                    continue
                target2 = target - num[i]
                for j in xrange(i+1, len(num)-2):
                    if num[j] > target2/3.0:
                        break
                    if j > i+1 and num[j] == num[j-1]:
                        continue
                    k = j + 1
                    l = len(num) - 1
                    target3 = target2 - num[j]
                    # we should use continue not break
                    # because target3 changes as j changes
                    if num[k] > target3/2.0:
                        continue
                    if num[l] < target3/2.0:
                        continue
                    while k < l:
                        sum_value = num[k] + num[l]
                        if sum_value == target3:
                            result.append([num[i], num[j], num[k], num[l]])
                            kk = num[k]
                            k += 1
                            while k<l and num[k] == kk:
                                k += 1
                            
                            ll = num[l]
                            l -= 1
                            while k<l and num[l] == ll:
                                l -= 1
                        elif sum_value < target3:
                            k += 1
                        else:
                            l -= 1
            return result
    

    We can reduce run time by adding some restrictions.


  • 0
    S

    if num[k] > target3/2.0:
    break
    if num[l] < target3/2.0:
    continue
    because as the increase of j, target3 will be decreased further. when num[k] is larger than target3/2.0, not need to increment j.


  • 0
    G

    Even thouth num[k] is larger than target3/2.0, still need to increment j. For example num[j=2] must be no more than num[k=10], but you cannot make sure that num[j=3]+num[k=4]>num[j=2]+num[j=10]. So still need to iterate j.


  • 0
    T

    thanks for sharing!! The four restrictions reduces my run time from 1700+ms down to 170ms. such a great change!


  • 0

    Nice idea! It would be perfect if you could pick better variable names.


Log in to reply
 

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