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

时间:2021-2-26 作者:admin

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

文章目录

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

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


Nsum问题

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

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

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

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

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

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

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

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。