题目

牛客网 - 和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出：

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

思路

意思就是求小于一个数的连续子序列和

例如，5

2 3

例如，9

2 3 4 
4 5 

例如，10

1 2 3 4

例如，15 ：

1 2 3 4 5 
4 5 6 
7 8

序列小于给出的整数，可以想到可以考虑用滑动窗口算法来做：

• 定义两个左右指针，代表活动窗口的边界
• 右指针不断往前移动，一旦碰到窗口内的值大于目标值了，就让左指针移动，并更新窗口内的值
• 一旦滑动窗口的值符合条件，就把窗口内的值依次加入结果集合里面
• 窗口的结束条件是左指针大于右指针或者右指针到边界了

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
         if (sum == 0 || sum == 1) {
             return result;
        }
        // 滑动窗口，设定头尾指针
        int pStart = 1;
        int pEnd = 1;
        int cur = 0;
        while (pStart <= pEnd && pEnd <= sum) {
            // 滑动窗口更新值
            cur += pEnd;
            
            // 左指针前移，并且更新滑动窗口的值
            while (cur > sum) {
                cur -= pStart;
                pStart++;
            }
            // 滑动窗口的值符合条件
            if (cur == sum && pStart != pEnd) {
                ArrayList<Integer> list = new ArrayList<>(pEnd - pStart + 1);
                for (int i = pStart; i <= pEnd; i++) {
                    list.add(i);
                }
                result.add(list);
            }
            // 右指针不断往右移动
            pEnd++;
        }
        return result;
    }
}

总结

万得笔试第二道，重新刷一遍，当是复习滑动窗口了