4Sum O(N^2) solution python code


  • 1
    H

    use a dictionary to store all the 2Sum results. and then use this dictionary to get all 4Sum results. the time complexity is O(N*N).

    class Solution(object):
        ### my own code, run time is O(N*N)
        def fourSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[List[int]]
            """
            #nums.sort()
            length = len(nums)
            d = dict()
            for i in xrange(length):
                for j in xrange(i+1, length):
                    val = nums[i] + nums[j]
                    if val in d:
                        d[val].append((i,j))
                    else:
                        d[val] = [(i,j)]
            res = set()
            for k in d:
                val = target - k
                if val in d:
                    vlist = d[val]
                    klist = d[k]
                    for (i,j) in vlist:
                        for (l,m) in klist:
                            ilist = [i,j,l,m]
                            if len(set(ilist)) != len(ilist):
                                continue
                            mylist = [nums[i], nums[j], nums[l], nums[m]]
                            mylist.sort()
                            res.add( tuple(mylist) )
            return list(res)
    

  • 0
    H

    Any one know how to post code in easy reading format?
    @house3618 said in 4Sum O(N^2) solution python code:

    class Solution(object):

    my own code, run time is O(N*N)

    def fourSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[List[int]]
    """
    #nums.sort()
    length = len(nums)
    d = dict()
    for i in xrange(length):
    for j in xrange(i+1, length):
    val = nums[i] + nums[j]
    if val in
    d[val].append((i,j))
    else:
    d[val] = [(i,j)]
    res = set()
    for k in
    val = target - k
    if val in
    vlist = d[val]
    klist = d[k]
    for (i,j) in vlist:
    for (l,m) in klist:
    ilist = [i,j,l,m]
    if len(set(ilist)) != len(ilist):
    continue
    mylist = [nums[i], nums[j], nums[l], nums[m]]
    mylist.sort()
    res.add( tuple(mylist) )
    return list(res)
    }


  • 0

    @house3618 please read this:
    https://discuss.leetcode.com/topic/22/welcome-new-users-please-read-this-before-posting

    Btw this is not the right place to post solution.


  • 0
    C

    said in 4Sum O(N^2) solution python code:

    class Solution(object):
    ### my own code, run time is O(N*N)
    def fourSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[List[int]]
    """
    #nums.sort()
    length = len(nums)
    d = dict()
    for i in xrange(length):
    for j in xrange(i+1, length):
    val = nums[i] + nums[j]
    if val in d:
    d[val].append((i,j))
    else:
    d[val] = [(i,j)]
    res = set()
    for k in d:
    val = target - k
    if val in d:
    vlist = d[val]
    klist = d[k]
    for (i,j) in vlist:
    for (l,m) in klist:
    ilist = [i,j,l,m]
    if len(set(ilist)) != len(ilist):
    continue
    mylist = [nums[i], nums[j], nums[l], nums[m]]
    mylist.sort()
    res.add( tuple(mylist) )
    return list(res)

    Clever but the running time doesn't decrease obviously. And the method is not general, just for 4 sum questions.

    However, it's enlightened


Log in to reply
 

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