【C++】算法集锦(8):从两数和问题拓展到一百数和问题

举报
看,未来 发表于 2021/02/23 23:41:45 2021/02/23
【摘要】 文章目录 2sum问题3sum问题Nsum问题 2sum问题 给定一个数组,以及一个数,从数组里随即找两个数加起来等于给定的那个数。 找出每组符合条件的数(不可重复)。 这表述没有问题吧。 那,这样的题目该怎么实现呢? 如果看过上一篇,的上一篇的小伙伴应该很快就能想到用双指针吧(其实那篇我就想写这个了,但是想了想,还是憋住了) 这里有两个...

在这里插入图片描述

2sum问题

给定一个数组,以及一个数,从数组里随即找两个数加起来等于给定的那个数。
找出每组符合条件的数(不可重复)。

这表述没有问题吧。

那,这样的题目该怎么实现呢?

如果看过上一篇,的上一篇的小伙伴应该很快就能想到用双指针吧(其实那篇我就想写这个了,但是想了想,还是憋住了)

这里有两个地方要注意:
1、数组要有序
2、跳过同类项

然后,就没什么难度了吧,我把伪代码写一下:

def two_sum(sum,nums):
	ret = []
	sz = len(nums)
	i = 0
	j = sz-1
	while i<j:
		if nums[i]+nums[j] == sum: ret.append([nums[1],nums[j]])
		elif nums[i]+nums[j] > sum: while nums[j-1] == nums[j]: j-=1 j-=1
		else: while nums[i+1] == nums[i]: i+=1 i+=1 return ret

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

3sum问题

两数和解决了,接下来就该轮到三数和问题了。三数和,其实就是两数和的一个增强版本,那么,我们需要做的就是:将三数和降维到两数和。

如何降维呢?其实也不难,就是拿一个数钉在数组(标兵)中,剩下两个数和最终目标减去标兵值,就是两数和嘛。

这里需要注意:
1、target = target - nums[flag]
2、如果target<0,立即停止
3、新数组区间:nums[flag+1:]

捋一下,然后我们来实现:

def three_sum(sum,nums):
	sz = len(nums)
	ret = []
	for flag in nums:
		if sum<=flag: return ret ret.append(flag,two_sum(sum-flag,nums[flag+1:])) return ret

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10


Nsum问题

三数和解决了,四数和呢?
那不是和三数和一个道理嘛,钉住一个,就变成三数和了。

那五数和呢?钉住一个,变四数和。
六数呢?七数呢?···· N数呢?

不就这样一路向下递归了嘛。

这里啊,有个小变通。
如果数组长度不够(这个上面倒是忘了,这里说一下)

如果N比数组长度的一半要长,那不妨反过来,先对数组求和,接下来你懂得。

在这里插入图片描述

在这里插入图片描述

文章来源: lion-wu.blog.csdn.net,作者:看,未来,版权归原作者所有,如需转载,请联系作者。

原文链接:lion-wu.blog.csdn.net/article/details/113981598

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200