leetcode 16题
重点在于优化以避免重复
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums = sorted(nums)
L = len(nums)
minDiff = sum(nums[:3]) - target
for i in range(L):
if i and nums[i] == nums[i-1]: continue #第一个数相等则跳过
a = nums[i]
midTarget = target - a
b, c = i+1, L-1 #去除重复,剩余两数范围为[i+1,L-1]
while b < c:
diff = nums[b]+nums[c] - midTarget
if diff == 0:
return target
minDiff = diff if abs(diff) < abs(minDiff) else minDiff
if diff < 0:
b += 1 #left移动一次
while b < c and nums[b] == nums[b-1]: b += 1#相等则继续移动
else:
c -= 1 #right移动一次
while b < c and nums[c] == nums[c+1]: c -= 1#相等则继续移动
return target + minDiff
相似题目:leetcode 18题 四数之和
nums中寻找不重复的 a+b+c+d = targetclass Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
L = len(nums)
res = []
if L <4: return res
nums = sorted(nums)
if sum(nums[:4]) > target or sum(nums[-4:] ) < target: return res
for i in range(L-3):
if i and nums[i] == nums[i-1]: continue
if sum(nums[i:i+4]) > target: return res
if sum(nums[-3:]) < (target-nums[i]): continue
a = nums[i]
for j in range(i+1,L-2):
if j > i+1 and nums[j] == nums[j-1]: continue
if sum(nums[-2:]) < (target-a-nums[j]):continue
if sum(nums[j:j+3]) > (target-a): break
b = nums[j]
p,q = j+1, L-1
while p < q:
c,d = nums[p], nums[q]
diff = (a+b+c+d) - target
if not diff:
res.append([a,b,c,d])
p += 1
q -= 1
while p < q and nums[p] == nums[p-1]: p += 1
while p < q and nums[q] == nums[q+1]: q -= 1
elif diff <0:
p += 1
while p < q and nums[p] == nums[p-1]: p += 1
else:
q -= 1
while p< q and nums[q] == nums[q+1]: q -= 1
return res
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)