都是比较经典的双指针问题,我们可以从中总结一些双指针的规律
首先这两题如果en做的话就是 \(O(n^{3})\) 的算法,暴力去找。但是我们可以发现这三个值是满足一定约束的,所以考虑使用方法将它降到 \(O(n^2)\) 。如果双指针,一个在头,一个在尾,两个向中间夹,根据约束条件合理选择向中间夹的策略,就能把三维降到二维。代码如下。与此题类似的还有前面的选择两个木板使得容积最大的问题,也可以使用双指针的方法解决。
#Leetcode 15
from ast import List
class Solution:
def threeSum(self, nums):
n = len(nums)
nums.sort()
if n < 2 or not nums:
return []
ans = []
for i in range(n):
if nums[i] > 0:
return ans
L = i+1
R = n-1
if i>0 and nums[i]==nums[i-1]:
continue
while (L < R):
if nums[i]+nums[L]+nums[R] == 0:
ans.append([nums[i], nums[L], nums[R]])
while (L < R and nums[L+1] == nums[L]):
L += 1
while (L < R and nums[R-1] == nums[R]):
R -= 1
L += 1
R -= 1
elif (nums[i]+nums[L]+nums[R] > 0):
R -= 1
else:
L += 1
return ans
if __name__ == "__main__":
nums = [-1, 0, 1, 2, -1, -4]
ans = Solution().threeSum(nums=nums)
print(ans)
#leetcode 16
from ast import List
class Solution:
def threeSumClosest(self, nums: List, target: int) -> int:
n = len(nums)
nums.sort()
if n < 2 or not nums:
return []
ans = 10000000000000000
for i in range(n):
L = i+1
R = n-1
while (L < R):
if abs(nums[i]+nums[L]+nums[R]-target)<abs(ans-target):
ans = nums[i]+nums[L]+nums[R]
if nums[i]+nums[L]+nums[R] == target:
return target
elif (nums[i]+nums[L]+nums[R] > target):
R -= 1
else:
L += 1
return ans
# 对于找三个数使其达到所需目标的问题,如果是暴力找的话需要n^3的复杂度
# 但是如果将其排序了,我们就可以使用双指针, 对其进行夹逼
# 因为这三个数是满足一定约束的, 因此可以把复杂度降到 n^2
if __name__ == "__main__":
nums = [0,0,0]
target = 1
ans = Solution().threeSumClosest(nums=nums,target=target)
print(ans)
标签:__,15,target,nums,16,ans,return,Leetcode,指针
From: https://www.cnblogs.com/keximeiruguo/p/17255614.html