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

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)
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``````

• 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.

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

• This post is deleted!

• 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).

• Yes, not strictly O(n^2).

• 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

• 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).

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