My O(N**2) simple solution, only one Loop(O(N**2)), using Hash


  • 0
    D
    1. using pairs of N*N to transfer the problem to 2-sum problem.
    2. if a matched pairs exist, when you index the second items, the first exist in index, so we can check and index items in one N**2 loop.

    Here is my AC codes:

        _result = []
        _dic = {}
    
        # rank for the non-descending-order of the result
        num.sort()
    
        for i in range(len(num)):
            for j in range(i+1, len(num)):
                _ijsum = num[i] + num[j]
    
                #judge whether pairs exist in hash structure
                if target - _ijsum in _dic:
                    for (a,b) in _dic[target - _ijsum]:
                        # a must be smaller than i, so b<i guarantee (a,b,i,j)
                        # follow the non-descending order
                        if b<i and [num[a], num[b],num[i], num[j]] not in _result:
                            _result.append([num[a],num[b],num[i],num[j]])
    
                if _ijsum in _dic:
                    _dic[_ijsum].append((i,j))
                else:
                    _tem = []
                    _tem.append((i,j))
                    _dic[_ijsum] = _tem
    
       return _result

  • 0
    A

    I think it is insufficient to just store the indices for each twoSum. Consider an example where input array is [0,0,0,0,0], and the target is zero. Then first four and last four elements are all valid quadruples, however, we should only return one of them.


  • 0
    A

    Sorry, I didn't notice the line [num[a], num[b],num[i], num[j]] not in _result ..


  • -3
    P
    This post is deleted!

  • 0
    L

    seems not a strict O(n^2) solution. For a specific pair (i, j), the hash could contain a non-constant number of pairs that make the two sum equals to target (i.e. _dic[target - ijsum] contains non-constant number of pairs).


  • 0
    D

    Yes, not strictly O(n^2).


  • 0
    S

    There is O(n^2) solution, but using a lot more memory. Here is a post in stack overflow : http://stackoverflow.com/questions/14732277/quadratic-algorithm-for-4-sum


  • 0
    P

    The general k-sum problem is referenced in the same post. http://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem. The optimal solution is O(N^2 logN).


Log in to reply
 

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