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

  • 0
    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
        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:
                if _ijsum in _dic:
                    _tem = []
                    _dic[_ijsum] = _tem
       return _result

  • 0

    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

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

  • -3
    This post is deleted!

  • 0

    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

    Yes, not strictly O(n^2).

  • 0

    There is O(n^2) solution, but using a lot more memory. Here is a post in stack overflow :

  • 0

    The general k-sum problem is referenced in the same post. 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.