首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指offer | 面试题44:和为s的连续整数序列

剑指offer | 面试题44:和为s的连续整数序列

作者头像
千羽
发布2022-02-23 15:39:41
3440
发布2022-02-23 15:39:41
举报
文章被收录于专栏:程序员千羽程序员千羽

死磕算法系列文章

  1. 干货 | 手撕十大经典排序算法
  2. 剑指offer | 认识面试
  3. 剑指offer | 面试题2:实现Singleton模式
  4. 剑指offer | 面试题3:二维数组的查找
  5. 剑指offer | 面试题4:替换空格
  6. 剑指offer | 面试题5:从尾到头打印链表
  7. 剑指offer | 面试题6:重建二叉树
  8. 剑指offer | 面试题7:用两个栈实现队列
  9. 剑指offer | 面试题8:旋转数组的最小数字
  10. 剑指offer | 面试题9:斐波那契数列
  11. 剑指offer | 面试题10:青蛙跳台阶问题
  12. 剑指offer | 面试题11:矩阵覆盖
  13. 剑指offer | 面试题12:二进制中1的个数
  14. 剑指offer | 面试题13:数值的整数次方
  15. 剑指offer | 面试题14:打印从1到最大的n位数
  16. 剑指offer | 面试题15:删除链表的节点
  17. 剑指offer | 面试题16:将数组中的奇数放在偶数前
  18. 剑指offer | 面试题17:链表中倒数第k个节点
  19. 剑指offer | 面试题18:反转链表
  20. 剑指offer | 面试题19:合并两个有序链表
  21. 剑指offer | 面试题20:判断二叉树A中是否包含子树B
  22. 剑指offer | 面试题21:二叉树的镜像
  23. 剑指offer | 面试题22:顺时针打印矩阵
  24. 剑指offer | 面试题23:包含min函数的栈
  25. 剑指offer | 面试题24:栈的压入、弹出序列
  26. 剑指offer | 面试题25:从上到下打印二叉树
  27. 剑指offer | 面试题26:二叉搜索树的后序遍历序列
  28. 剑指offer | 面试题27:二叉树中和为某一值的路径
  29. 剑指offer | 面试题28:复杂链表的复制
  30. 剑指offer | 面试题29:二叉搜索树转换为双向链表
  31. 剑指offer | 面试题30:字符串的排列
  32. 剑指offer | 面试题31:数组中出现次数超过一半的数字
  33. 剑指offer | 面试题32:最小的k个数
  34. 剑指offer | 面试题33:连续子数组的最大和
  35. 剑指offer | 面试题34:1~n 整数中 1 出现的次数
  36. 剑指offer | 面试题35:把数组排成最小的数
  37. 剑指offer | 面试题36:丑数
  38. 剑指offer | 面试题37:第一个只出现一次的字符
  39. 剑指offer | 面试题38:数组中的逆序对
  40. 剑指offer | 面试题39:两个链表的第一个公共节点
  41. 剑指offer | 面试题40:数组中数字出现的次数
  42. 剑指offer | 面试题41:二叉树的深度
  43. 剑指offer | 面试题42:平衡二叉树
  44. 剑指offer | 面试题43:和为s的两个数字

Leetcode : https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_44_findContinuousSequence/Solution.java

剑指 Offer 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]]

方法:滑动窗口(双指针)

设连续正整数序列的左边界 ii 和右边界 jj ,则可构建滑动窗口从左向右滑动。循环中,每轮判断滑动窗口内

元愫和与目标值 target 的大小关系,若相等则记录结果,若大于 target 则移动左边界 i (以减小窗口内的元 素和),若于 target 则移动右边界 j (以增大窗口内的元素和) 。

算法流程:

  1. 初始化:左边界 i = 1,右边界 j = 2,元素和 s = 3,结果列表 res ;
  2. 循环:
    • 当 i ≥ j时跳出;
    • 当s > target时:向右移动左边界 i = i + 1 ,并更新元素和 s ;
    • 当s < target时:向右移动右边界 j = j + 1,并便新元索和 s ;
    • 当s = target时:记绿连续整数序列,饷右移动左边界 i = i + 1 ;
  3. 返回值:返回结果列表 res ;

复杂度分析;

  • 时间复杂度:由于两个指针移动均单调不减,且最多移动| target / 2 | 次,即方法一提到的枚举的上界,所 以时间复杂度为 O(target) 。
  • 空间复杂度:O(1) ,除了答案数组织需要常数的空间存放若干变量。
package com.nateshao.sword_offer.topic_44_findContinuousSequence;

import java.util.ArrayList;
import java.util.List;

/**
 * @date Created by 邵桐杰 on 2022/1/25 15:37
 * @微信公众号 千羽的编程时光
 * @个人网站 www.nateshao.cn
 * @博客 https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:
 */
public class Solution {
    public static void main(String[] args) {
        int[][] findContinuousSequence = findContinuousSequence(9);
        for (int[] ints : findContinuousSequence) {
            for (int anInt : ints) {
                System.out.println("anInt = " + anInt);
            }
        }
    }

    /**
     * 解法:滑动窗口(双指针)
     * @param target
     * @return
     */
    public static int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while (i < j) {
            if (s == target) {
                int[] ans = new int[j - i + 1];
                for (int k = i; k <= j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            if (s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }

}

参考链接:https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/jian-zhi-offer-57-ii-he-wei-s-de-lian-xu-t85z/

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2022-01-28,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 千羽的编程时光 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 剑指 Offer 57 - II. 和为s的连续整数序列
  • 方法:滑动窗口(双指针)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档