Leecode 面试题57 - II. 和为s的连续正数序列

简介: Leecode 面试题57 - II. 和为s的连续正数序列

题目描述:

输入一个正整数 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

来源:力扣(LeetCode)

链接: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

解题思路:这里需要了解一下滑动窗口的解题方法

注意事项:

如何利用呢?

示例如下:

示例解析:

public int[][] findContinuousSequence(int target) {
    int i = 1; // 滑动窗口的左边界
    int j = 1; // 滑动窗口的右边界
    int sum = 0; // 滑动窗口中数字的和
    List<int[]> res = new ArrayList<>();
    while (i <= target / 2) {
        if (sum < target) {
            // 右边界向右移动
            sum += j;
            j++;
        } else if (sum > target) {
            // 左边界向右移动
            sum -= i;
            i++;
        } else {
            // 记录结果
            int[] arr = new int[j-i];
            for (int k = i; k < j; k++) {
                arr[k-i] = k;
            }
            //将数组加入到res集合中
            res.add(arr);
            // 左边界向右移动
            sum -= i;
            i++;
        }
    }
  //将res集合转换成为数组
    return res.toArray(new int[res.size()][]);
}


相关文章
|
6天前
Leecode之面试题消失的数字
Leecode之面试题消失的数字
|
10月前
【牛客面试必刷TOP101】有效括号序列、滑动窗口的最大值
【牛客面试必刷TOP101】有效括号序列、滑动窗口的最大值
|
11月前
|
机器学习/深度学习 人工智能 自动驾驶
强化学习从基础到进阶--案例与实践含面试必知必答[10]:模仿学习、行为克隆、逆强化学习、第三人称视角模仿学习、序列生成和聊天机器人
强化学习从基础到进阶--案例与实践含面试必知必答[10]:模仿学习、行为克隆、逆强化学习、第三人称视角模仿学习、序列生成和聊天机器人
强化学习从基础到进阶--案例与实践含面试必知必答[10]:模仿学习、行为克隆、逆强化学习、第三人称视角模仿学习、序列生成和聊天机器人
|
11月前
|
C++
剑指Offer - 面试题7:重构二叉树 (力扣 - 105、从前序与中序遍历序列构造二叉树)
剑指Offer - 面试题7:重构二叉树 (力扣 - 105、从前序与中序遍历序列构造二叉树)
42 0
|
11月前
|
机器学习/深度学习 人工智能 算法
强化学习从基础到进阶-常见问题和面试必知必答[1]:强化学习概述、序列决策、动作空间定义、策略价值函数、探索与利用、Gym强化学习实验
强化学习从基础到进阶-常见问题和面试必知必答[1]:强化学习概述、序列决策、动作空间定义、策略价值函数、探索与利用、Gym强化学习实验
|
11月前
Leecode 面试题62. 圆圈中最后剩下的数字
Leecode 面试题62. 圆圈中最后剩下的数字
47 0
|
11月前
|
存储
Leecode 面试题 17.16. 按摩师
Leecode 面试题 17.16. 按摩师
43 0
|
11月前
Leecode面试题40. 最小的k个数
Leecode面试题40. 最小的k个数
44 0
|
11月前
Leecode 面试题 01.06. 字符串压缩
Leecode 面试题 01.06. 字符串压缩
30 0
|
11月前
|
存储
Leecode面试题43. 1~n整数中1出现的次数
Leecode面试题43. 1~n整数中1出现的次数
50 0