劍指Offer之和為S的連續正數序列
題目描述
小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100。但是他並不滿足於此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)。沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22。現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列? Good Luck!
思路:滑動窗口(雙指針)
1 import java.util.ArrayList; 2 public class Solution { 3 public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { 4 ArrayList<ArrayList<Integer>> array=new ArrayList<>(); 5 int plow=1,phigh=2; 6 while(phigh>plow) { 7 int psum=(phigh+plow)*(phigh-plow+1)/2; 8 if(psum==sum) { 9 ArrayList<Integer> list=new ArrayList<>(); 10 for(int i=plow;i<=phigh;i++) 11 list.add(i); 12 array.add(list); 13 plow++; 14 } 15 else if(psum<sum) 16 phigh++; 17 else 18 plow++; 19 } 20 return array; 21 } 22 }