剑指offer33 JZ74 和为S的连续正数序列

思路

• 我们可以从数字1开始枚举连续的数字，将其累加判断其是否等于目标，如果小于目标数则继续往后累加，如果大于目标数说明会超过，跳出，继续枚举下一个数字开始的情况（比如2，比如3），这样每次都取连续的序列，只有刚好累加和等于目标数才可以记录从开始到结束这一串数字，代表是一个符合的序
• 而因为序列至少两个数，每次枚举区间的起始数字最多到目标数的一半向下取整即可，因为两个大于目标数一半的数相加一定大于目标数。

具体做法：

• step 1：从1到目标值一半向下取整作为枚举的左区间，即每次序列开始的位置。
• step 2：从每个区间首部开始，依次往后累加，如果大于目标值说明这一串序列找不到，换下一个起点。
• step 3：如果加到某个数字刚好等于目标值，则记录从区间首到区间尾的数字。

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
        int sum1 = 0;
        //因为序列至少两个数，因此枚举最多到该数字的一半向下取整
        int up = (sum - 1) / 2; 
        //枚举左区间
        for(int i = 1; i <= up; i++){ 
            //从左区间往后依次连续累加
            for(int j = i; ;j++){ 
                sum1 += j;
                //大于目标和则跳出该左区间
                if(sum1 > sum){ 
                    sum1 = 0;
                    break;
                //等于则找到
                }else if(sum1 == sum){ 
                    sum1 = 0;
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    //记录线序的数字
                    for(int k = i; k <= j; k++) 
                        temp.add(k);
                    res.add(temp);
                    break;
                }
            }
        }
        return res;
    }
}