I'm trying to map this problem into a 4-sum problem, and I find the time complexity is always \$O(n^3)\$. Is there a way to optimize time complexity, with constant additional space complexity \$O(1)\$?
Any other advice about improvement for time complexity, code bugs or code style advice is appreciated.
Problem
Given an array A of unique integers, find the index of values that satisfy A + B =C + D, where A,B,C & D are integers values in the array. Find all combinations of quadruples.
def four_sum (numbers, target, start, end, exclude_index_set):
i = start
j = end
result = []
while i < j:
if i in exclude_index_set:
i += 1
elif j in exclude_index_set:
j -= 1
elif numbers[i] + numbers[j] == target:
result.append((numbers[i], numbers[j]))
i += 1
j -= 1
elif numbers[i] + numbers[j] > target:
j -= 1
else:
i += 1
return result
if __name__ == "__main__":
numbers = [1,2,3,4]
result = []
for i,v in enumerate(numbers):
for j in range(i+1, len(numbers)):
r = four_sum(numbers, v+numbers[j], i+1, len(numbers)-1, set([i,j]))
if len(r) > 0:
r.append(([numbers[i],numbers[j]]))
result.append(r)
print result
A, B, C
, there can be at most oneD
that solves the equation. If duplicates were allowed, then up ton-3
values ofD
could solve the equation. \$\endgroup\$ – JS1 Feb 7 '17 at 9:43n[a]+n[b] == n[a]+n[b]
andn[a]+n[b] == n[b]+n[a]
for anya,b
in the index range, so there's always at least \$2N(N-1)\$ quadruples in the solution, where \$N\$ – the input array's length. \$\endgroup\$ – CiaPan Feb 7 '17 at 13:47