【C++】算法集锦（8）：从两数和问题拓展到一百数和问题

文章目录

• • 2sum问题
  • 3sum问题
  • Nsum问题

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比数组长度的一半要长，那不妨反过来，先对数组求和，接下来你懂得。