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; } }