《剑指offer》之和为S的连续正数序列

Myth丶恋晨 2023-07-04 15:31 9阅读 0赞

前言

今天刷的一道题目是是关于穷举的。

题目

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

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

分析

这里参考了答案区的思路,这个思路算是很厉害的,窗口的双指针的思路。窗口的左右两边就是两个指针,我们根据窗口内值之和来确定窗口的位置和宽度。
以sum=15为例吧,
初始left=1;right=2;和add=1+2=3;
addsum,所以left++,
此时left=3,add=3+4+5+6=18;
add>sum,所以left++,
此时left=4,add=4+5+6=15;
add=sum ,将这组记录下来,继续left++;
此时left=5,rigt=6;add=5+6=11;
addsum,所以left++,
此时left=6,rigt=7;add=6+7=14;
addsum,所以left++,
此时left=7,rigt=8;add=7+8=21;
add=sum ,将这组记录下来,继续left++;
此时left=8,rigt=8;left>=right,循环结束退出,这时我们就可以得到三组满足条件的序列啦。

通过上面的例子,思路算是非常清楚了,主要是左右两个指针,当left<right 就执行循环体。循环体做的事情就是,先求left加到right 的和。

  1. add=(left+right)*(right-left+1)/2;

这个求和很好算吧,等差数列就和

  1. add=(a1+an)*n/2
  2. a1=left;
  3. an=right;
  4. n=right-left+1;
  5. 代替上去就可以了。

然后就比较add 与sum 的大小,如果add< sum ,则右指针right右移一位,如果add>sum,则左指针右移一位,如果add=sum,就表明该组是我们想要的,记录下来,同时l左指针右移一位,继续查找其他。
当left>=right的时候就退出循环体。

解法

  1. public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
  2. ArrayList<ArrayList<Integer> > lists = new ArrayList<> ();
  3. int left=1;
  4. int right=2;
  5. while(left<right){
  6. int add=(left+right)*(right-left+1)/2;
  7. if(add==sum){
  8. ArrayList<Integer> list=new ArrayList<>();
  9. for(int i=left;i<=right;i++){
  10. list.add(i);
  11. }
  12. lists.add(list);
  13. left++;
  14. }else if(add<sum){
  15. right++;
  16. }else {
  17. left++;
  18. }
  19. }
  20. return lists;
  21. }

测试

main 方法

  1. public static void main(String[] args) {
  2. Solution solution= new Solution();
  3. ArrayList<ArrayList<Integer>> lists=solution.FindContinuousSequence(15);
  4. for(ArrayList<Integer> list:lists){
  5. for(Integer tmp:list){
  6. System.out.print(tmp+"\t");
  7. }
  8. System.out.println();
  9. }
  10. }

在这里插入图片描述
再测一个100的
在这里插入图片描述
在这里插入图片描述

发表评论

表情:
评论列表 (有 0 条评论,9人围观)

还没有评论,来说两句吧...

相关阅读