和为S的连续正数序列数学技巧,事半功倍
和为S的连续正数序列(数学技巧，事半功倍)
和为S的连续正数序列
数学的基础在算法中的用处大概就是对数字的敏感性了，如果能找到数字的规律，在求解数字的时候往往就能根据规律快速求解。而普通的程序思维相比数学思维，一般就略微显得暴力。
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
题目分析
这个题目也算得上是给你一个数计算机能玩一天的题目，我们仍然从直观的思维开始一步步深入分析。
要求这个序列，我们可以逐个数字去找从
i i
i 开始的序列，显然
i
0 i>0
i
0 ，但是我们也没有必要所有序列都去找，毕竟以
i i
i 开始的序列，最多只有一个等于S，如果我们发现以
i i
i 开始，以
j j
j 结尾的序列和大于等于S了，显然后面就不用找了。此外，序列最少要包括两个数，显然如果
i ≥ S 2 i≥\frac{S}{2}
i
≥
2
S
，那么两个数之和肯定大于S了，此时我们也不用找了。我们求和的时候每一次序列多一个数，所以求和的复杂度是
O ( 1 ) O(1)
O
(
1
) ，但是我们要找多少个序列，这个问题的复杂度就是多少，大致是
O ( S l g S ) O(SlgS)
O
(
S
l
g
S
) 的。
双指针/滑动窗口法
我们要表示一个连续序列，我们只需要知道两个数的位置就够了，只需要知道从开始开始，到哪里结束。既然使用双指针的思想，那就可以参考 。我们使用两个指针，一个记录序列的开始，一个记录序列的结束。
如果两个指针记录的序列和小于S，则说明应该增大和，需要往序列里面添加数字，此时记录结尾的指针就需要后移，纳入更多的数字。如果序列和大于S，那么说明以序列开头的数字不可能存在和为S的序列了。此时需要减少数字，则开头指针后移。如果和等于S，则把这个序列记录，然后开头指针后移。这样的操作不会漏掉满足需求的值原理和引用的文章类似，有兴趣可以回去查看。
我们来看一个例子，以S=9为例。初始化前指针pBeg=1,后指针pEnd=2。
| pBeg | pEnd | sum 状态 S | 下一步操作 |
|---|---|---|---|
| 1 | 2 | 3小于9 | pEnd++ |
| 1 | 3 | 6小于9 | pEnd++ |
| 1 | 4 | 10大于9 | pBeg++ |
| 2 | 4 | 9等于9(保存) | pBeg++ |
| 3 | 4 | 7小于9 | pEnd++ |
| 3 | 5 | 12大于9 | pEnd++ |
| 4 | 5 | 9等于9(保存) | pBeg++，pBeg==5退出 |
熟悉了这个过程，差不多可以写出代码了。
C++代码
class Solution {
public:
vector<vector<int>> FindContinuousSequence(int S) {
vector<vector<int>> res;
int pBeg = 1, pEnd = 2,sum=3,mid=S>>1;
while (pBeg <= mid)
{
if(sum>=S)
{
if (sum == S)
{
vector<int> tmp;
for (int i = pBeg; i <= pEnd; i++)tmp.push_back(i);
res.push_back(tmp);
}
sum -= pBeg;
pBeg += 1;
}
else
{
pEnd += 1;
sum += pEnd;
}
}
return res;
}
};python代码
class Solution:
def FindContinuousSequence(self, S):
pBeg = 1
pEnd = 2
middle = (S + 1)>>1
curSum = 3
output = []
while pBeg < middle:
if curSum >= S:
if curSum == S:
output.append(range(pBeg, pEnd + 1))
curSum -= pBeg
pBeg += 1
else:
pEnd += 1
curSum += pEnd
return output这里用的还是双指针或者叫滑动窗口的技巧求解，因为两个指针都是单向前进，没有回溯的过程，所以这个时间复杂度很好分析，就是
O ( S ) O(S)
O
(
S
) 了，这个技巧还是蛮重要的，可以看到相比第一种分析复杂度已经进步了不少，因为这里已经利用了和的比较关系，省去了很多计算。
纯数学技巧法
如果我们觉得上面的方法还是在找连续序列的和，这个方法就可以说是直接计算了。我们都知道如果让我们去求连续序列的和，我们肯定会知道一个公式，(首项+尾项)*项数/2。但是这里需要怎么用上这个公式呢。
我们假设序列的首项是i，尾项是j。我们可以轻易求出
s u m
( i + j ) ( j − i + 1 ) / 2 sum=(i+j)(j-i+1)/2
s
u
m
=
(
i
j
)
(
j
−
i
1
)
/
2 ，我们把2移到等式左边可以得到
2 s u m
( i + j ) ( j − i + 1 ) 2sum=(i+j)(j-i+1)
2
s
u
m
=
(
i
j
)
(
j
−
i
1
) ，显然我们有点二年级的数学水平就知道
( i + j ) 和 ( j − i + 1 ) (i+j)和(j-i+1)
(
i
j
)
和
(
j
−
i
1
) 一个是奇数，一个是偶数。那现在就容易多了，我们直接求出sum的所有奇数因子，那么显然所有的奇数因子就构成了一组或两组解。可以通过质因数分解，把所有的质因数任意组合则得到所有的质数因子。
为什么是一组或者两组，因为可能i解出来是个负数。我们不妨设这个奇数因子是odd，那么显然那个偶数因子就是
s u m ∗ 2 / o d d sum*2/odd
s
u
m
∗
2
/
o
d
d ，这个时候用两个数列两个方程：
{ o d d
i + j 2 s u m o d d
j − i + 1 a n d { o d d
i + j 2 s u m o d d
j − i + 1 \left { \begin{aligned} odd & = & i+j \ \frac{2sum}{odd} & = & j-i+1 \ \end{aligned} \qquad and \qquad \right. \left { \begin{aligned} odd & = & i+j \ \frac{2sum}{odd} & = & j-i+1 \ \end{aligned} \right.
⎩
⎨
⎧
o
d
d
o
d
d
2
s
u
m
=
=
i
j
j
−
i
1
a
n
d
⎩
⎨
⎧
o
d
d
o
d
d
2
s
u
m
=
=
i
j
j
−
i
1
通过这两个方程求解出
i i
i 和
j j
j ，然后舍去不符合条件的数值。如果这是一道选择题，到这里也就结束了。我下面给出一个参考代码。只知道在大数测试上，双指针根本无法等待出结果，这个方法很快就能算出来。因为需要质因数分解，难以评估复杂度，代码中需要保存下来的质数可以用于后续计算，这样计算的次数越多，省下来的时间就越多。
class Solution:
prim = [2, 3, 5, 7, 11]
def primeFactorization(self, tsum):
for i in range(self.prim[-1]+1,int(tsum**0.5),2):
flag=True
for j in self.prim:
if i%j==0:
flag=False
break
if flag:
self.prim.append(i)
i=0
fac=[]
while i<len(self.prim):
if tsum%self.prim[i]:
i+=1
continue
fac.append(self.prim[i])
tsum/=self.prim[i]
return fac
def FindContinuousSequence(self, tsum):
fac=self.primeFactorization(tsum)
odd=[i for i in fac if i%2]
fact=set()
res=[]
mul=lambda x,y:x*y
for i in range(len(odd)):
l=permutations(odd,i+1)
for j in l:
a=reduce(mul,j)
fact.add(a)
fact.add((tsum<<1)//a)
fact=sorted(list(fact))
for i in fact:
j=tsum*2//i
if i<j+1:
continue
res.append(list(range((i-j+1)>>1,(i+j+1)>>1)))
return res这种方法仅供参考，有利于思维方式的提高。总之一句话，数学能力在算法分析中会起到至关重要的作用，之中能力是需要慢慢累积出来的。