Concise python solution with pruning


  • 4
    def threeSumSmaller(self, nums, target):
        ans = 0
        nums = sorted(nums)
        for i in xrange(len(nums)-2):
            prev_ans = ans                 # for pruning
            j,k = i+1, len(nums)-1
            while j<k:
                if nums[i] + nums[j] + nums[k] < target:
                    ans += (k-j)
                    j += 1
                else:
                    k -= 1
            if prev_ans == ans:
                break                   #if the ans doesn't change, then larger i won't change ans either
        return ans

  • 1
    A

    Nice observation! This check helps me beat 93% submissions.:)


Log in to reply
 

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