脚本宝典收集整理的这篇文章主要介绍了20211108-04 Four Sum,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
https://leetcode-cn.com/problems/4sum/submissions/
思路:n个数之和,n-2重for循环 + 双指针
python
class Solution(object):
def fourSum(self, nums, target):
if len(nums) < 4:
return []
res = []
nums.sort()
for i in range(len(nums) - 3): # 第一个元素只需要遍历 0...n-3 就行
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, len(nums) - 2):
if j > i + 1 and nums[j] == nums[j-1]:
continue
new_tgt = target - nums[i] - nums[j]
left, right = j + 1, len(nums) - 1
while left < right:
if nums[left] + nums[right] == new_tgt:
res.append( [nums[i], nums[j], nums[left], nums[right]] )
left, right = left + 1, right - 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif nums[left] + nums[right] < new_tgt:
left += 1
else:
right -= 1
return res
以上是脚本宝典为你收集整理的20211108-04 Four Sum全部内容,希望文章能够帮你解决20211108-04 Four Sum所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。