题目描述： 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
import java.util.ArrayList; public class FindContinuousSequence { //暴力枚举 public ArrayList<ArrayList<Integer> > FindContinuousSequenceWithVia(int sum){ ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); for(int i = 1;i <= sum / 2; i++){ for(int j = i + 1; j < sum; j++){ int tmp = 0; for(int k = i; k <= j; k++){ //求数列和 tmp += k; } if(tmp == sum){ ArrayList<Integer> list1 = new ArrayList<>(); for(int k = i; k <= j; k++){ list1.add(k); } list.add(list1); }else if(tmp > sum){ break; } } } return list; } } import java.util.ArrayList; public class FindContinuousSequence02 { public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); int tmp = 0; for(int i = 1; i <= sum / 2; i++){ for(int j = i; j < sum; j++){ tmp += j; if(tmp == sum){ ArrayList<Integer> list1 = new ArrayList<>(); for(int k = i; k <= j; k++){ list1.add(k); } list.add(list1); }else if(tmp > sum ){ tmp = 0; break; } } } return list; } } import java.util.ArrayList; /* 滑动窗口法 */ public class FindContinuousSequence03 { public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>(); int tmp = 0; int L = 1; int R = 1; while (L <= sum / 2 ){ if(tmp < sum){//扩大窗口 tmp += R; R++; }else if(tmp > sum){//缩小窗口 tmp -= L; L++; }else{ ArrayList<Integer> list1 = new ArrayList<>(); for(int k = L; k < R; k++){ list1.add(k); } list.add(list1); tmp -= L; L++; } } return list; } }