class Solution: # @return a list of lists of length 4, [[val1,val2,val3,val4]] def fourSum(self, num, target): num.sort() result =  for i in xrange(len(num)-3): if num[i] > target/4.0: break if i > 0 and num[i] == num[i-1]: continue target2 = target - num[i] for j in xrange(i+1, len(num)-2): if num[j] > target2/3.0: break if j > i+1 and num[j] == num[j-1]: continue k = j + 1 l = len(num) - 1 target3 = target2 - num[j] # we should use continue not break # because target3 changes as j changes if num[k] > target3/2.0: continue if num[l] < target3/2.0: continue while k < l: sum_value = num[k] + num[l] if sum_value == target3: result.append([num[i], num[j], num[k], num[l]]) kk = num[k] k += 1 while k<l and num[k] == kk: k += 1 ll = num[l] l -= 1 while k<l and num[l] == ll: l -= 1 elif sum_value < target3: k += 1 else: l -= 1 return result
We can reduce run time by adding some restrictions.
if num[k] > target3/2.0:
if num[l] < target3/2.0:
because as the increase of j, target3 will be decreased further. when num[k] is larger than target3/2.0, not need to increment j.
Even thouth num[k] is larger than target3/2.0, still need to increment j. For example num[j=2] must be no more than num[k=10], but you cannot make sure that num[j=3]+num[k=4]>num[j=2]+num[j=10]. So still need to iterate j.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.