class Solution(object):
def fourSum(self, nums, target):
n = len(nums)
if n < 4:
return []
nums = sorted(nums)
combo = [None, None, None, None]
res = []
i = 0
while i <= n4 and nums[i]*4 <= target:
combo[0] = nums[i]
j = i + 1
while j <= n3 and nums[j]*3 + nums[i] <= target:
combo[1] = nums[j]
p = j + 1
q = n  1
while p < q and nums[j] + nums[i] + nums[p]*2 <= target:
combo[2] = nums[p]
combo[3] = nums[q]
if sum(combo) <= target:
res.append(combo[:]) if sum(combo) == target else None
while p < q and nums[p] == combo[2]:
p += 1
else:
while q > p and nums[q] == combo[3]:
q = 1
while j <= n3 and nums[j] == combo[1]:
j += 1
while i <= n4 and nums[i] == combo[0]:
i += 1
return res
Why is Python O(n^3) TLE


class Solution: def fourSum(self, nums, target): index_pairs = dict() combos = dict() n = len(nums) for i in range(0,n): for j in range(i+1,n): sum = nums[i] + nums[j] if index_pairs.get(target  sum) is not None: for pair in index_pairs[target  sum]: if i != pair[0] and i != pair[1] and j != pair[0] and j != pair[1]: # Avoid overuse combo = sorted((nums[i], nums[j], nums[pair[0]], nums[pair[1]])) # Avoid duplicate combos[tuple(combo)] = True if index_pairs.get(sum) is not None: index_pairs[sum].append((i,j)) else: index_pairs[sum] = [(i,j)] return combos.keys()
And I wonder why there isn't discussion on O(n^2) time O(n^2) space solution?
Though this only beats 55%
