A conise python solution based on ksum


  • 6
    H
    class Solution:
        # @return a list of lists of length 4, [[val1,val2,val3,val4]]
        def fourSum(self, num, target):
            num.sort()
            def ksum(num, k, target):
                i = 0
                result = set()
                if k == 2:
                    j = len(num) - 1
                    while i < j:
                        if num[i] + num[j] == target:
                            result.add((num[i], num[j]))
                            i += 1
                        elif num[i] + num[j] > target:
                            j -= 1
                        else:
                            i += 1
                else:
                    while i < len(num) - k + 1:
                        newtarget = target - num[i]
                        subresult = ksum(num[i+1:], k - 1, newtarget)
                        if subresult:
                            result = result | set( (num[i],) + nr for nr in subresult)
                        i += 1
                    
                return result
            
            return [list(t) for t in ksum(num, 4, target)]

  • 3
    H

    Generator version:

    def fourSum(self, num, target):
        num.sort()
        def ksum(num, k, target):
            i = 0
            if k == 2:
                j = len(num) - 1
                while i < j:
                    if num[i] + num[j] == target:
                        yield (num[i], num[j])
                        i += 1
                    elif num[i] + num[j] > target:
                        j -= 1
                    else:
                        i += 1
            else:
                while i < len(num) - k + 1:
                    newtarget = target - num[i]
                    for sub in ksum(num[i+1:], k - 1, newtarget):
                        yield (num[i],) + sub
                    i += 1
        
        return [list(t) for t in set(ksum(num, 4, target))]
    

  • 0
    A

    your algorithm is very good. I like them very much. Your idea is different from mine, my idea is 2Sum + 2Sum = 4Sum. But I think your idea is better, because yours is more general. Moreover, generator was used in your code of version 2, inspired by this, I think I should begin to learn python more deeply.


Log in to reply
 

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