登录
  • #刷题
  • #leetcode

3S‌‌‍‍‌‍‍‌‍‍‌‍‍‌‍‍‌‍‍‌‍‍‌‌‌‍‍‌‍‌‍‍um With Multiplicity 解法的效率问题

李浩泉
462
0
[mw_shl_code=python,true]while left < right:

if A + A[left] + A
== target:[/mw_shl_code]

上面这个我写的CODE,在LC上无法通过,显示:Time Limit Exceeded

[mw_shl_code=python,true]diff = target - A

while left < right:

sum = A[left] + A


if sum == diff:[/mw_shl_code]

改成这个样子,LC就通过了,为什么呢?

[mw_shl_code=python,true]def threeSumMulti(self, A, target):

"""

:type A: List[int]

:type target: int

:rtype: int

"""

result = 0

A.sort()

for i in range(len(A)-2):

left = i + 1; right = len(A) - 1

diff = target - A

while left < right:

sum = A[left] + A


if sum == diff:

if A[left] == A
:

result = (result + (right-left+1)*(right-left) // 2) % (10**9 + 7)

left += 1; right -= 1

break

left_count, right_count = 1, 1

while left < right and A[left] == A[left+1]:

left += 1

left_count += 1

while left < right and A
== A[right-1]:

right -= 1

right_count += 1

result = (result + left_count * right_count) % (10**9 + 7)

left += 1; right -=1

elif sum < diff:

left += 1

else:

right -= 1

return result[/mw_shl_code]
0条回复
热度排序

发表回复