| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 305 人关注过本帖
标题:顺序表中找两数之和
只看楼主 加入收藏
丘山君
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:87
专家分:154
注 册:2017-11-15
结帖率:54.55%
  已结贴   问题点数:30  回复次数:3   
顺序表中找两数之和
在一个升序的数据集合中,在该集合中查找两个数之和为k。
有重复值,除了两重循环遍历,大佬们有没有什么方法
我想了个但是有问题
例如:33367888,和要求为11,这里应该是有9组
想过用两个下标i,j分别从数组两端开始,
通过判断两数相加是否等于k,等于,则i走一步,再判断;不等于,j走;
但是发现不对,会出现漏组情况
求帮忙给个思路,谢谢;
2017-12-02 00:39
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:50
帖 子:4972
专家分:13940
注 册:2016-10-22
  得分:10 
思路方向应该是可以的~漏组是因为重复数出现使得指针过早偏离了~可以在原基础上改进一下算法
~

相等时j偏离一位直到出现不相等的数,记录偏离了a个数~
然后i偏离一位直到出现不相等的数,记录偏离b个数~

然后组数为a*b;

例如计算

112333和为4

112333
 i          j

112333
 i        j



112333
i       j

112333
   i j

112333
   i j

112333
     i
     j

i==j结束循环~

j走了3格,i走了两格,共有6组~


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-12-02 05:30
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:157
帖 子:6123
专家分:26729
注 册:2014-5-20
  得分:10 
组合问题,两重循环或递归遍历就可以。
有些看似是一个循环,但在循环体内通过判断改变i、j,其实也是多次遍历。
2017-12-02 07:56
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:260
帖 子:5789
专家分:32992
注 册:2011-1-18
  得分:10 
补充一下其它的,不等于的时候,还得考虑是大于还是小于
考虑 1 5 6 7
小于时动i,大于时动j
2017-12-02 09:55







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020956 second(s), 8 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved