python - 将 N-Sum 减少为两个和
问题描述
我最近遇到了一个很酷的算法,可以将“在一个数组中查找 n 个数字与目标相加”之类的任何问题减少为二和问题。但是,我很难理解一行代码。
def findNsum(nums, target, N, result, results):
if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
l,r = 0,len(nums)-1
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(len(nums)-N+1):
if i == 0 or (i > 0 and nums[i-1] != nums[i]):
findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
results = []
findNsum(sorted(nums), 0, 3, [], results)
return results
条件:
if i == 0 or (i > 0 and nums[i-1] != nums[i]):
对我来说没有意义。为什么我要检查if nums[i-1] != nums[i]
?如果我尝试使用,例如,使用nums = [-1, 0, 1, 2, 2, -1, -4]
,我会得到[[-4, 2, 2], [-1, -1, 2], [-1, 0, 1]]
条件。如果我把它拿出来,我会得到[[-4, 2, 2], [-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]
。任何人都可以理解这一点吗?
干杯!
解决方案
条件nums[i-1] != nums[i]
是避免在选择第一个元素时创建重复的解决方案,这可以在第二个示例的输出中看到。这个问题想要找到所有唯一的解决方案,而不是所有可能的解决方案,因此我们想要删除第二个[-1,0,1]
推荐阅读
- python - 使用 2 个参数计算列表中单词的函数
- c# - ILDASM和ILASM,如何使用它们?
- android - 如何使用 NFC 发送简单的字符串
- javascript - 如何将变量传递给另一个php文件?
- flutter - 在模拟器中查看 Flutter 小部件测试
- database - 使用 Parse Server 的社交网络应用程序的数据库建议
- json - Python json 错误列表索引必须是整数
- python - Selenium webdriver - TypeError:“模块”对象不可调用
- jquery - 引导卡折叠不起作用
- python - 在 Python 中实现跳转搜索的结果不正确