题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序思路
思路1:滑动窗口法(区间连续,双指针同向移动)。用两个数small和big分别表示序列的最小值和最大值,首先把small初始化为1,big初始化为2.如果从small到big的序列的和大于s,则从序列中去掉较小的值,也就是增大small的值。如果从small到big的序列的和小于s,则可以增大big,让这个序列包含更多的数字。因为这个序列至少要有两个数字,我们一直增加small到(1+s)/2为止。
思路2:还可以尝试数学分析法。
解法1
import java.util.ArrayList; public class Solution { // 版本1 public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer> > res = new ArrayList<>(); int small = 1, big = 2; //两个起点,相当于动态窗口的两边 while (small < big){ // small < (sum + 1) / 2 也能通过 int tempSum = (small + big)*(big - small + 1) / 2; if (tempSum == sum){ ArrayList<Integer> list = new ArrayList<>(); // 每次用的时候new一个,这样就不需要用完list.clear()了 for (int i = small; i <= big; i++) { list.add(i); } res.add(list); big++; }else if (tempSum > sum){ //如果当前窗口内的值之和大于sum,那么左边窗口右移一下 small++; }else{ //如果当前窗口内的值之和小于sum,那么右边窗口右移一下 big++; } } return res; } // 版本2 // 与版本1相比不同之处:求连续序列的和,因此可以在前一个序列和的基础上求操作之后的序列的和。 public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer> > res = new ArrayList<>(); int small = 1, big = 2; //两个起点,相当于动态窗口的两边 int tempSum = small + big; while (small < big){ // small < (sum + 1) / 2 也能通过 if (tempSum == sum){ ArrayList<Integer> list = new ArrayList<>(); for (int i = small; i <= big; i++) { list.add(i); } res.add(list); big++; tempSum += big; }else if (tempSum > sum){ //如果当前窗口内的值之和大于sum,那么左边窗口右移一下 tempSum -= small; small++; }else{ //如果当前窗口内的值之和小于sum,那么右边窗口右移一下 big++; tempSum += big; } } return res; } }
解法2
M一下,以后再做可以试试用数学的思路解一下。
自己写的暴力遍历法
import java.util.ArrayList; public class Solution { // 思路就是根据等差数列求和公式(count*(a1+an))/2,遍历起始位置a1,然后遍历count,看是否满足题意 // 测试用例,输入15;输出1~5 、4~6 、7~8 public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer> > res = new ArrayList<>(); ArrayList<Integer> list = new ArrayList<>(); for (int i = 1; i <= sum / 2 + 1; i++) { int num = i; int counts = sum / 2 + 1; while (counts >= 2){ if (counts*(num+num+counts-1)/2 == sum){ // 核心 for (int j = num; j <=num+counts-1;j++) list.add(j); res.add(new ArrayList<>(list)); list.clear(); break; } counts--; } } return res; } }
收获
如果需要多次使用ArrayList添加数据,可以在每次用的时候new一个新的,这样就不用共用一个,用完list.clear()了。