LeetCode.剑指offer.057.和为s的连续正数序列

题目描述

《剑指offer》面试题57 - II. 和为s的连续正数序列
https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：
1 <= target <= 10^5

---

解题过程

利用求和公式遍历序列个数

等差数列求和公式

$
S_n = a_1 + a_2 + … + a_n = na_1 + \frac{n(n-1)}{2}d
$

已知公差d=1，则有
$
S_n = a_1 + a_2 + … + a_n = na_1 + \frac{n(n-1)}{2}
$

已知sn，和每次循环时固定的n，直接可得到 a1 的值，然后从 a1 开始以等差 1 递增 n 次即可得到一个合法序列。
当 a1 不是整数时，跳过循环；当 sn 不够减时，结束循环。

n 最多循环 √target 次，每次里面的小循环也需要 n 次(也就是 √target 次) ，所以总的时间复杂度是 O(target)

private static class SolutionV2020 {
    public int[][] findContinuousSequence(int sn) {
        LinkedList<List<Integer>> listList = new LinkedList<>();
        // n: 等差序列的个数，从2开始往上找
        for (int n = 2; ; n++) {
            // 等差数列求和公式 sn = na1 + dn(n-1)/2，已知公差d=1，则有 sn = na1 + n(n-1)/2，已知sn，每次循环时的n，直接可得到a1
            int na1 = sn - n * (n-1) / 2;
            // 结束循环
            if (na1 <= 0) {
                break;
            }
            // 无法整除n，跳过
            if ((na1 % n) != 0) {
                continue;
            }
            int a1 = na1 / n;
            List<Integer> seqList = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                seqList.add(a1++);
            }
            listList.addFirst(seqList);
        }
        int[][] ret = new int[listList.size()][];
        int count = 0; // 序列个数
        for (List<Integer> seq : listList) {
            ret[count++] = seq.stream().mapToInt(Integer::intValue).toArray();
        }
        return ret;
    }
}

滑动窗口

窗口 sum[i,j] = target，则 左边界 i 右移继续找下一个
sum[i,j] < target， 则 右边界 j 右移扩大 sum
sum[i,j] > target， 则 左边界 i 右移缩小 sum
时间复杂度 O(target)，空间复杂度 O(1)

---

GitHub代码

algorithms/leetcode/offer/_057_ContiguousIntegerSequenceOfSumS.java
https://github.com/masikkk/algorithms/blob/master/leetcode/offer/_057_ContiguousIntegerSequenceOfSumS.java

---