jz57_2.和为s的连续正数序列

题目描述

题解

滑动窗口

这道题要求的是连续子序列, 所以使用滑动窗口的思想比较合适.

滑动窗口由两个指针划出的区域组成, 两个指针只能向同一个方向移动, 在同一时间只能移动一个指针.

当窗口的整数和小于目标值, 就移动右指针, 每移动一次, 窗口的整数和都要增大

当窗口的整数和小于目标值, 就移动左指针, 每移动一次, 窗口的整数和都要减小

若窗口的整数和与目标值相等, 就将次时窗口内的整数组成的数组添加到结果集中

public int[][] findContinuousSequence(int target) {
    List<int[]> res = new ArrayList<>();
    int i = 1;
    int j = 2;
    int windowSum = i;

    while (j <= target / 2 + 1) {
        windowSum += j;
        while (i < j && windowSum >= target) {
            if (windowSum == target) {
                int[] temp = new int[j - i + 1];
                for (int k = 0; k < j - i + 1; k++) {
                    temp[k] = i + k;
                }
                res.add(temp);
                break;
            } else if (windowSum > target) {
                windowSum -= i;
                i++;
            }
        }
        j++;
    }
    return res.toArray(new int[0][]);
}