Concise solution using python. Set, list comprehension used in code. O(n^3)


  • 0
    A
    class Solution:
        # @return a list of lists of length 4, [[val1,val2,val3,val4]]
        def fourSum(self, num, target):
            if num is None or target is None:
                return []
    
            num.sort()
            res = set()
            num_len = len(num)
    
            if num_len < 4:
                return []
    
            left_right = [(x,y) for x in range(num_len) for y in range(num_len) if y-x >= 3]
    
            for left_out,right_out in left_right:
                left_in = left_out + 1
                right_in = right_out - 1
                mid_sum1 = num[left_out] + num[right_out]
                mid_t = target - mid_sum1
    
                while left_in<right_in:
                    mid_sum2 = num[left_in] + num[right_in]
                    if mid_sum2 == mid_t:
                        res.add((num[left_out], num[left_in], num[right_in], num[right_out]))
                        right_in -= 1
                        left_in += 1
                    else:
                        if mid_sum2 > mid_t:
                            right_in -= 1
                        else:
                            left_in += 1
    
            res = [list(x) for x in res]
    
            return res

  • 0
    O

    For reference, my code with complexity also to be O(n^3).

    class Solution:
    # @param {integer[]} nums
    # @param {integer} target
    # @return {integer[][]}
    def fourSum(self, nums, target):
        ln = len(nums)
        if ln < 4:
            return []
        ans = []
        nums.sort()
        for i in range(ln-3):
            for j in range(i+3, ln):
                m, n, add2V = i+1, j-1, nums[i] + nums[j]
                while (m < n):
                    add4V = add2V + nums[m] + nums[n]
                    if add4V == target:
                        ans.append((nums[i], nums[m], nums[n], nums[j]))
                        m += 1
                    elif add4V > target:
                        n -= 1
                    else:
                        m += 1
        return list(set(ans))

Log in to reply
 

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