题解 | #剑指offer JZ74 和为S的连续正数序列#

* 思路1：穷举。

• 题目中的连续正数序列即为公差为1的等差递增数列，在此对应的求和公式为：Sn=(a1+an)(an-a1+1)/2；
• 由于序列要求至少包括两个数，序列内按照从小至大的顺序；
• 我采取的策略是每次遍历的时候固定a1（首项），寻找符合条件的an（尾项）；
• 注意观察到符合条件的最后一组序列存在一种规律，a1在范围**[ 1, sum/2 ]**内取值，作为外层循环，首项不会超过sum的一半，尾项不超过sum的一半加1，利用好这个规律 遍历的时候可缩小范围。（建议结合下面的代码和推理理解）
• 时间复杂度O(n^2)

代码（JAVA实现）

public class Solution {
	 public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
	       ArrayList<ArrayList<Integer>> res=new ArrayList<>();
	       if(sum<2) return res;
	       for(int left=1;left<=sum/2;left++) {//等差数列首项a1=left
	    	   for(int right=sum/2+1;right>left;right--) {//等差数列尾项an=right
	    		   if(sum*2==(left+right)*(right-left+1)) {
	    			   ArrayList<Integer> list=new ArrayList<>();
	    			   for(int k=left;k<=right;k++) list.add(k);
	    			   res.add(list);
	    		   }
	    		   //left固定时，right最大的时候等差数列的和都比sum小，right--后更不可能相等
	    		   else if(sum*2>(left+right)*(right-left+1)) break;
	    	   }
	       }
	       return res;
	    }
}

/*

* 思路2：滑动窗口。

• 扩大窗口，right += 1
• 缩小窗口，left += 1

算法步骤：

1.  初始化，left=1,right=1, 表示窗口大小为0
   

2.  如果窗口内值的和小于目标值sum， 表示需要扩大窗口，right += 1
   

3.  否则，如果窗口内的值的和大于目标值sum，表示需要缩小窗口，left += 1
   

4.  否则，等于目标值，存结果，缩小窗口，继续进行步骤2,3,4
   

代码（JAVA实现）

public class Solution {
 public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum){
		 ArrayList<ArrayList<Integer>> res=new ArrayList<>();
	       if(sum<2) return res;
	       int left=1,right=1;//left窗口左边界，right窗口右边界，初始窗口大小为0,[left,right)
	       int content=0;//滑动窗口内的元素和
	       while(left<=sum/2){//要求至少包括两个数,左边界到sum的一半即可
	    	   if(content<sum) {//扩大窗口
	    		   content+=right;//加入窗口右侧的元素后，再扩大窗口
	    		   right++;
	    	   }
	    	   else if(content>sum){//缩小窗口
	    		   content-=left;
	    		   left++;
	    	   }
	    	   else {//和为sum
	    		   ArrayList<Integer> list=new ArrayList<>();
	    		   for(int k=left;k<right;k++) {//注意left在窗口内，而right不在窗口内，k是小于而不是小于等于right
	    			   list.add(k);//逐个添加到list
	    		   }
	    		   res.add(list);//加入到结果数组
                 content-=left;//减去窗口最左侧的元素，继续寻找
	    		   left++;
	    	   }
	       }
	       return res;
	 }
}