首页 > 其他分享 >LeetCode 18:2 sum 方法在计算 4 sum 中的应用(基于 2 指针的二进制搜索)

LeetCode 18:2 sum 方法在计算 4 sum 中的应用(基于 2 指针的二进制搜索)

时间:2022-08-31 03:01:30浏览次数:105  
标签:10 rptr nums 18 sum two lptr LeetCode

LeetCode 18:2 sum 方法在计算 4 sum 中的应用(基于 2 指针的二进制搜索)

我们得到一个输入数组,我们有一个目标。我们要找出数组表单中哪两个元素的值等于目标。

例子:
数字= [1,2,3,4,5,6,7]
目标 = 10
输出:[[3,7],[4,6]]

约束:
约束是应该对 nums 进行排序以应用两个总和。

方法
与二分查找(二分)相同,我们有两个指针,lptr 和 rptr。
lptr 指向起始索引, rptr 指向最后一个索引。

image.png

现在,让我们看看这里存在的模式:
仔细观察这两种情况,

情况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。

image.png

这使得总和为 9。再次需要增加总和。

image.png

完成,我们得到 10
nums[lptr] = 3 和 nums[rptr] = 7. 并且 nums[lptr]+nums[rptr]=10

现在,我们不需要 lptr 之前的元素,同样需要 rptr 旁边的元素。因此我们增加 lptr 并减少 rptr。

lptr += 1
rptr -= 1

image.png

同样,这是形成 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

相关文章

  • AGC018
    A答案为POSSIBLE当且仅当\(k\le\maxa_i\wedge\gcda_i\midk\),时间复杂度\(\mathcal{O}(n\logn)\)。B首先钦定所有的都选,每次去掉人数最多的并更新答案,时间......
  • [Google] LeetCode 715 Range Module 线段树
    ARangeModuleisamodulethattracksrangesofnumbers.Designadatastructuretotracktherangesrepresentedashalf-openintervalsandqueryaboutthem.......
  • leetcode704基本二分查找
    intsearch(vector<int>&nums,inttarget){intl=0;intr=nums.size()-1;cout<<r<<endl;intmid;while(l<r){mid=(l+r)/2;......
  • leetcode35二分查找并插入
    intsearchInsert(vector<int>&nums,inttarget){intl=0;intr=nums.size();intmid=0;while(l<r){mid=(l+r)/2;......
  • leetcode278二分变形
    longlongfirstBadVersion(intn){longlongl=1;longlongr=n;longlongmid=1;//执行完之后l=r即为答案while(l<r){......
  • leetcode-998. 最大二叉树 II
    998.最大二叉树II图床:blogimg/刷题记录/leetcode/998/刷题代码汇总:https://www.cnblogs.com/geaming/p/16428234.html题目思路看到树就要想到递归。解法/***D......
  • 大道如青天,协程来通信,Go lang1.18入门精炼教程,由白丁入鸿儒,Go lang通道channel的使
    众所周知,Golang的作用域相对严格,数据之间的通信往往要依靠参数的传递,但如果想在多个协程任务中间做数据通信,就需要通道(channel)的参与,我们可以把数据封装成一个对象,然后把......
  • 微软有史以来最重的软件:超过 18 公斤
    微软有史以来最重的软件:超过18公斤投递人 itwriter 发布于2022-08-2914:10 评论(0) 有1676人阅读 原文链接 [收藏] « »今天的软件都是数字化的,没有......
  • P4592 [TJOI2018]异或
    有一颗以\(1\)为根节点的由\(n\)个节点组成的树,节点从\(1\)至\(n\)编号。树上每个节点上都有一个权值\(v_i\)。现在有\(q\)次操作,操作如下:\(1~x~z\):查询节点......
  • leetcode 28. Implement strStr() 实现 strStr()(简单)
    一、题目大意实现strStr()函数。给你两个字符串haystack和needle,请你在haystack字符串中找出needle字符串出现的第一个位置(下标从0开始)。如果不存在,则返回......