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