Python：输出总和为目标总和的所有范围

Question

题：

给定 K 由非零、非负整数 1 到 K 组成，输出总和等于 K 的所有范围/区间。

例如，如果 K 等于 6，那么输出应该是[[1,3], [6,6]]。对于[1,3], 1+2+3 = 6 和 对于[6,6], 6 = 6。

我的解决方案

下面是我的解决方案，但我认为时间复杂度是 O(N2)。有没有更有效的方法来做到这一点？

def targetSum(k):
  nums = list(range(1,k+1))
  res = []
  for end in range(len(nums)):
    start = 0
    while start <= end:
      sumhere = sum(nums[start:end+1])
      if sumhere == k:
        res.append([nums[start], nums[end]])
      start+=1
  return res

targetSum(6)

Answer 1

您可以O(sqrt(K))使用一些数学方法及时解决此问题。

范围和是差1的等差数列之和，所以我们可以写公式

K = n/2 * (2*a + n - 1) or
2 * K = n * (2*a + n - 1) 

其中n是范围大小，a是起始值

所以我们遍历所有可能的因式分解2*K成两个因数2*K = p * q ，并求解简单系统

n = p
2*a + n - 1 = q

或者

2*a + p - 1 = q
a  = (q + 1 - p) / 2

请注意，解决方案存在于不同奇数/偶数/奇偶性的除数（这里哪个术语更好？）（否则a不是整数），并且q必须大于p（以获得正数a） - 这个事实允许更早地停止循环。

K=6 的示例：

2K = 12
1 * 12 :  n = 1, a = 6   (range 6..6)
2 * 6:   no solution (both even) 
3 * 4:    n = 3, a = 1  (range 1..3)

简单的实现（对于非常大的值，它比@hilberts_drinking_problem 实现慢一点（两倍））

def findranges(k):
    n = 1
    kk = 2 * k
    res = []
    while n * n < kk:
        if kk % n == 0:
            q = kk // n
            if (q ^ n) & 1: //compare parity using the least significant bit
                a = (q + 1 - n) // 2
                res.append([a, a + n - 1])
        n += 1
    return res

print(findranges(60))