JZ74 和为S的连续正数序列

题目

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













。 现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?

方法1 枚举法

思路

算法实现

从数字1开始枚举连续的数字               ，将其累加判断其是否等于目标
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  ， 如果小于目标数则继续往后累加














， 如果大于目标数说明会超过 
  
  
  
  
  
  
  
，跳出
  
  
  
  
  
  
  
 ， 继续枚举下一个数字开始的情况（比如2
 


 


 


 


 


 


 


 ，比如3） 
 
 
 
 
 
 
 
， 这样每次都取连续的序列
   
   
   
   
   
   
   
 ，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字
 

 

 

 

 

 

 

 ，代表是一个符合的序列 
  
  
  
  
  
  
  
。 具体做法： step 1：从1到目标值一半向下取整作为枚举的左区间 

 

 

 

 

 

 

 
，即每次序列开始的位置
  
  
  
  
  
  
  
 。 step 2：从每个区间首部开始               ，依次往后累加

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，如果大于目标值说明这一串序列找不到














，换下一个起点
 


 


 


 


 


 


 


 。 step 3：如果加到某个数字刚好等于目标值                       ，则记录从区间首到区间尾的数字 
 
 
 
 
 
 
 
。

代码

package mid.JZ74和为S的连续正数序列; import java.util.ArrayList; public class Solution { /** * 枚举法 * @param sum * @return */ public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); if (sum == 0) return new ArrayList<>(); //因为序列至少两个数
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，因此枚举最多到该数字的一半向下取整 int sum1 = 0; int mid = (sum - 1) / 2; for (int i = 1; i <= mid; i++) { for (int j = i; ; j++) { sum1 += j; if (sum1 > sum) { sum1 = 0; break; } else if (sum1 == sum) { ArrayList<Integer> temp = new ArrayList<>(); for (int k = i; k <= j; k++) temp.add(k); res.add(temp); sum1 = 0; break; } } } return res; } }

方法2 滑动窗口（推荐使用）

思路

算法实现

从某一个数字开始的连续序列和等于目标数如果有






















，只能有一个               ，于是我们可以用这个性质来使区间滑动
   
   
   
   
   
   
   
 。 两个指针l
  
  
  
  
  
  
  
 、r指向区间首和区间尾
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，公式(l+r)∗(r−l+1)/2计算区间内部的序列和














， 如果这个和刚好等于目标数 
  
  
  
  
  
  
  
，说明以该区间首开始的序列找到了
  
  
  
  
  
  
  
 ，记录下区间内的序列
 


 


 


 


 


 


 


 ，同时以左边开始的起点就没有序列了 
 
 
 
 
 
 
 
，于是左区间收缩； 如果区间和大于目标数
   
   
   
   
   
   
   
 ，说明该区间过长需要收缩
 

 

 

 

 

 

 

 ，只能收缩左边； 如果该区间和小于目标数 

 

 

 

 

 

 

 
，说明该区间过短需要扩大               ，只能向右扩大

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 ，移动区间尾
 

 

 

 

 

 

 

 。 具体做法： step 1：从区间[1,2][1,2][1,2]开始找连续子序列 

 

 

 

 

 

 

 
。 step 2：每次用公式计算区间内的和














，若是等于目标数                       ，则记录下该区间的所有数字
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 ，为一种序列






















，同时左区间指针向右               。 step 3：若是区间内的序列和小于目标数               ，只能右区间扩展
  
 
  
 
  
 
  
 
  
 
  
 
  
 
  ，若是区间内的序列和大于目标数














，只能左区间收缩

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 。

代码

package mid.JZ74和为S的连续正数序列; import java.util.ArrayList; public class Solution { /** * 滑动窗口（推荐使用） * @param sum * @return */ public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); for (int l = 1, r = 2; l < r; ) { int sum1 = (l + r) * (r - l + 1) / 2; if (sum1 == sum) { ArrayList<Integer> temp = new ArrayList<>(); for (int i = l; i <= r; i++) { temp.add(i); } res.add(temp); l++; } else if(sum1 < sum) { r++; } else { l++; } } return res; } }