【剑指Offer】041——和为S的连续正数序列(数值)
2019-08-20 本文已影响1人
就问皮不皮
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
解题思路
滑动窗口的方法:用两个数字 start 和 end 分别表示序列的最小值和最大值,首先将 start 初始化为1,end 初始化为2。如果从start到end的和大于sum,我们就从序列中去掉较小的值(即增大start),相反,只需要增大end。终止条件为:一直增加start到(1+sum)/2并且end小于sum为止,这是其中暗含的条件,要计算sum不需要将end滑动到sum,因为sum/2+(sum+1)/2>sum(如果sum为奇数时:如sum=101, (sum+1)/2=51, 50+51=sum)。
参考代码
Java
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
// 至少两个数,那么从1开始,最小为3
if (sum < 3) return res;
int start = 1, end = 2, mid = (1+sum)/2; // mid用于缩小范围
while (start < mid){
int s = totalSum(start, end); // 计算当前窗口包含数字的和
if (s == sum){
res.add(getSequence(start, end));
end ++; // 窗口长度后移,在下次循环中窗口起始部分后移
}else if (s < sum) {
end++; // 不足,窗口长度后移
}else if (s > sum){
start ++; // 窗口起始后移,减小和
}
}
return res;
}
public int totalSum(int start, int end){
int sum = 0;
for (int i = start; i <= end; i++) sum += i;
return sum;
}
public ArrayList<Integer> getSequence(int start, int end){
ArrayList<Integer> temp = new ArrayList<>();
for (int i = start; i <= end; i++) temp.add(i);
return temp;
}
}
Python
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
res = []
if sum < 3 :return res
start, end, mid = 1, 2, (1+tsum)/2
while start < mid:
s = sum(range(start, end + 1))
if s == tsum:
res.append([i for i in range(start, end + 1)])
end += 1
elif s < tsum:
end += 1
elif s > tsum:
start += 1
return res
个人订阅号
image