和为S的连续正数序列

题目描述解法一思路 解法二思路

题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

解法一

时间O(n)，空间O(1)

思路

用数学的解法。 对于给定的一个数$S$来说，若一个数列的和为$S$，若使用$n$表示数列中的第一个数，那$S$一定满足这个式子。

$S=(n+0)+(n+1)+...+(n+m)$

其中$(n+m)$表示连续数组中最后一个数。 那么我们将上述式子整理一下 $S=(m+1)\ast n+1+2+...+m=(m+1)\ast n+m\ast (m+1)/2$ $n=(S-m\ast (m+1)/2)/(m+1)$ 通过题意我们可以知道确定$m$的最大值不会超过$S/2$，（若$m$超过$S/2$，那么数组之和必定超过$S$）。 那么通过一个$1-S/2$遍历，若计算出$n$为整数，则表示存在一个数组。

import java.util.ArrayList; import java.util.Comparator; public class Solution { public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { double n; ArrayList<ArrayList<Integer>> result = new ArrayList<>(); for(int m=1; m<=sum/2; m++){ n = (sum - m*(m + 1)/2)/(m+1.0); if(n > 0 && (int) n == n){ ArrayList<Integer> list = new ArrayList<>(); for(int i=0; i<=m; i++){ list.add((int)n + i); } result.add(list); } } result.sort(new Comparator<ArrayList<Integer>>() { @Override public int compare(ArrayList<Integer> list, ArrayList<Integer> list1) { if(list.get(0) > list1.get(0)){ return 1; } else if(list.get(0) < list1.get(0)){ return -1; } return 0; } }); return result; } }

解法二

时间O(n)，空间O(1)

思路

滑动窗口算法，初始化窗口左指针$left$和右指针$right$指到1处($sum$不会为0) 判断当前指针之内的元素之和$count$(闭区间)是否为$sum$，如果和小于$sum$，则右指针向右移动一格。若$count$大于$sum$，则左指针向右移动一格。若$count$等于$sum$将左右指针之间的数放入数组，并将左指针加一。 循环直到左指针走过$sum$的一半(若左指针超过$sum$的一半，那$count$的值必将大于$sum$)

import java.util.ArrayList; public class Solution { public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) { //初始化 int count = 1; int i = 1, j = 1; ArrayList<ArrayList<Integer> > result = new ArrayList<>(); while(i <= sum/2){ if(count == sum){ //如果窗口之和等于sum的值 ArrayList<Integer> list = new ArrayList<>(); for(int k=i; k<=j; k++){ list.add(k); } result.add(list); count -= i; i++; } else if(count < sum){ //若窗口之和小于sum值 j++;//右指针向右移 count += j;//count值改变 } else{ //若窗口之和大于sum值 count -= i;//count值改变 i++;//左指针向左移 } } return result; } }