# Share my python code, run time 200+- 20ms

• ``````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:
break
if num[l] < target3/2.0:
continue
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.

• thanks for sharing!! The four restrictions reduces my run time from 1700+ms down to 170ms. such a great change!

• Nice idea! It would be perfect if you could pick better variable names.

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