LeetCode 18:2 sum 方法在计算 4 sum 中的应用(基于 2 指针的二进制搜索)
我们得到一个输入数组,我们有一个目标。我们要找出数组表单中哪两个元素的值等于目标。
例子:
数字= [1,2,3,4,5,6,7]
目标 = 10
输出:[[3,7],[4,6]]
约束:
约束是应该对 nums 进行排序以应用两个总和。
方法
与二分查找(二分)相同,我们有两个指针,lptr 和 rptr。
lptr 指向起始索引, rptr 指向最后一个索引。
现在,让我们看看这里存在的模式:
仔细观察这两种情况,
情况1:
保持 rptr 不变并增加 lptr
(1+7) → 8
(2+7) → 9
(3+7) — -> 10
(4+7) — -> 11
案例二:
保持 lptr 不变并增加 rptr
(1+7) → 8
(1+6) → 7
(1+5) → 6
从上述两种情况,形成的模式是,如果 lptr 增加,则总和将增加,并且当 rptr 增加时,总和将减少(假设数组已排序)。
应用概念
现在,让我们将此方法应用于 2 个指针以找到目标 10。
步骤1
将 lptr 放在 0 索引处,将 rptr 放在最后一个索引处
数字 = 列表([1,2,3,4,5,6,7])
目标 = 10
lptr = 0
rptr = len(nums)-1
main_ls = []
第2步
我们将遍历元素
现在,nums[lptr] + nums[rptr] = 8。这小于 10,这意味着我们需要增加总和。如果要增加总和,我们需要移动 lptr。
这使得总和为 9。再次需要增加总和。
完成,我们得到 10
nums[lptr] = 3 和 nums[rptr] = 7. 并且 nums[lptr]+nums[rptr]=10
现在,我们不需要 lptr 之前的元素,同样需要 rptr 旁边的元素。因此我们增加 lptr 并减少 rptr。
lptr += 1
rptr -= 1
同样,这是形成 10,我们做 lptr+=1 和 rptr-=1。
现在,我们看到 lptr == rptr。但是问题陈述说总和应该是两个不同元素的形式。因此,我们打破了迭代。
因此,整个逻辑如下:
而(lptr
two_sum = nums[lptr]+nums[rptr]
如果 two_sum < 目标:
lptr+=1
elif two_sum > 目标:
rptr-=1
别的:
打印([nums[lptr],nums[rptr]])
lptr+=1
rptr-=1 [3, 7]
[4, 6]
现在,问题是如果我们在那个 nums 中有重复的元素,那么我们将不会得到一个唯一的集合
数字 = 列表([1,1,1,4,5,6,7,7])
目标 = 8
l = 0
r = len(nums)-1
main_ls = []
而(l
two_sum = nums[l]+nums[r]
如果 two_sum < 目标:
l+=1
elif two_sum > 目标:
r-=1
别的:
打印([数字[l],数字[r]])
l+=1
r-=1 [1, 7]
[1, 7]
现在,为了处理这个问题,我们必须递增直到出现这样的重复元素。
所以,我们保持这样的条件
而 nums[l] == prev 和 l
同样的方式
而 nums[r] == prev2 和 l
因此,整个逻辑看起来像这样,并在一个司机的情况下进行测试
数字 = 列表([1,1,1,1,7,7,7,7])
目标 = 8
l = 0
r = len(nums)-1
main_ls = []
而(l
two_sum = nums[l]+nums[r]
如果 two_sum < 目标:
上一页 = 数字 [l]
而 nums[l] == prev 和 l
elif two_sum > 目标:
上一页 = 数字 [r]
而 nums[r] == prev 和 l
别的:
打印(数字[l],数字[r])
上一页 = 数字 [l]
prev2 = 数字[r]
而 nums[l] == prev1 和 l
而 nums[r] == prev2 和 l 1 7
注意:这不会影响整体时间复杂度。它仅保持 O(n)。
感谢您阅读我的文章!!!
DMs 对任何问题开放!!! ( https://linktr.ee/prituldave )
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明
本文链接:https://www.qanswer.top/1942/51283102
标签:10,rptr,nums,18,sum,two,lptr,LeetCode From: https://www.cnblogs.com/amboke/p/16641551.html