>>> n = [1,2,3,4,5]
>>> for i,v in enumerate(n[:-2]): print(i,v)
...
0 1
1 2
2 3
>>>912ms beat:60%
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for left in range(len(nums)-2):
if left > 0 and nums[left] == nums[left - 1]:
continue
mid = left + 1
right = len(nums) - 1
while mid < right:
n = nums[left] + nums[mid] + nums[right]
if n < 0:
mid += 1
elif n > 0:
right -= 1
else:
res.append([nums[left], nums[mid], nums[right]])
while mid < right and nums[mid] == nums[mid + 1]: mid += 1
while mid < right and nums[right] == nums[right - 1]: right -= 1
mid += 1
right -= 1
return resclass Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = set()
for left in range(len(nums)-2):
if left > 0 and nums[left] == nums[left - 1]:
continue
d = {}
for val in nums[left + 1:]:
if val not in d:
d[-nums[left]-val] = 1
else:
res.add((nums[left], -nums[left]-val, val))
return map(list, res)思路： First I made a dictionary to keep track of the number of occurrences of each input value. Observe that no more than two instances of any given nonzero value can ever be used in a sum, so additional instances can be discarded. Three zeros can be used in a sum, but if we only have two zeros to work with, we can't use them together, so if we have only two zeros we can discard one of them.
On a second pass through the dictionary I checked all values x that occur twice to see if -2x also occurs. If not, they can't be used together so discard one of the x's.
Then I used the dictionary to build an ordered list of values, with duplicates to represent values that occur twice for nonzero values or three times in the case of zero. Note that the sum of the smallest two entries in the list implies ceiling on the largest useful value, while the sum of the largest two entries implies a floor on the smallest useful value. Values outside those bounds can be removed and this process was repeated until no change needed to be made on the final iteration. Example of successive iterations: [-10,-9,-5,-2,0,1,1,3,6,21,52] floor = -73, ceiling = 19 (remove 21,52) [-10,-9,-5,-2,0,1,1,3,6] floor = -9, ceiling = 19 (remove -10) [-9,-5,-2,0,1,1,3,6] floor = -9, ceiling = 14 (done)
Finally I looped through the list of values to find ordered (v1,v2) pairs such that v1 <= v2 and searched the dictionary for corresponding v3 = -(v1+v2). Except for (0,0,0) which I treated as a special case, the ordering requirements imply v1 < 0 so we break out of the outer loop as soon as v1 >= 0. Similarly we break out of the inner loop as soon as we find v3 < v2. Also since the list may have duplicates, we continue past any iterations in both the outer and inner loops where we just looped on the same value.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
instances = {}
for n in nums:
if n in instances:
instances[n] += 1
else:
instances[n] = 1
values = []
result = []
for n, count in sorted(instances.items()):
values.append(n)
if n == 0 and count >= 3:
result.append([0,0,0])
elif n != 0 and count >= 2:
third = -2*n
if third in instances:
if n < third:
result.append([n,n,third])
else:
result.append([third,n,n])
#any sums involving duplicate values were handled above
nvalues = len(values)
while nvalues >= 3:
floor = -(values[nvalues-1] + values[nvalues-2])
ceiling = -(values[0] + values[1])
if floor > ceiling:
return []
iLeft = nvalues
iRight = -1
for i in range(nvalues):
if values[i] >= floor:
iLeft = i
break
for i in range(nvalues-1, -1, -1):
if values[i] <= ceiling:
iRight = i
break
if iLeft == 0 and iRight == nvalues - 1:
break
values = values[iLeft:iRight+1]
nvalues = len(values)
if nvalues < 3:
return result
for i in range(nvalues-2):
v1 = values[i]
if v1 >= 0:
break
for j in range(i+1,nvalues-1):
v2 = values[j]
v3 = -(v1 + v2)
if v3 <= v2:
break
if v3 in instances:
result.append([v1,v2,v3])
return resultclass Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = set([])
plus = sorted([n for n in nums if n>0])
plus_c = set(plus)
zero = [n for n in nums if n == 0]
minus = sorted([n for n in nums if n<0])
minus_c = set(minus)
# all zero
if len(zero)>2:
ans.add((0,0,0))
# plus zero minus
if len(zero)>0:
for n in minus:
if -n in plus_c:
ans.add((n,0,-n))
# plus minus minus
n = len(minus)
for i in range(n):
for j in range(i+1,n):
diff = -(minus[i]+minus[j])
if diff in plus_c:
ans.add((minus[i],minus[j],diff))
# plus plus minus
n = len(plus)
for i in range(n):
for j in range(i+1,n):
diff = -(plus[i]+plus[j])
if diff in minus_c:
ans.add((diff,plus[i],plus[j]))
return list(ans)