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