当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.剑指offer.057.和为s的连续正数序列

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


上一篇 LeetCode.剑指offer.059.最大队列

下一篇 LeetCode.1103.Distribute Candies to People 等差数列分糖果

阅读
评论
544
阅读预计2分钟
创建日期 2020-03-06
修改日期 2020-03-06
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论