首页 > 其他分享 >【剑指 Offer】 57 - II. 和为s的连续正数序列

【剑指 Offer】 57 - II. 和为s的连续正数序列

时间:2023-04-16 09:22:52浏览次数:39  
标签:窗口 target Offer int 57 II 序列 滑动 sum

【题目】

输入一个正整数 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/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof

【思路】

滑动窗口

初始i=1,j=2 i为左边界,j为右边界
1.滑动窗口内的值<target j右移
 2.滑动窗口内的值=target 保存 i右移
3.滑动窗口内的值>target i右移
当i>=j时,结束循环

这题注意list和array的转换的写法

 

【代码】

class Solution {
    public int[][] findContinuousSequence(int target) {
        //滑动窗口
        //初始i=1,j=2 i为左边界,j为右边界
        // 1.滑动窗口内的值<target j右移
        // 2.滑动窗口内的值=target 保存 i右移
        // 3.滑动窗口内的值>target i右移
        // 当i>=j时,结束循环

        int i = 1, j = 2;
        int sum = 3;
        List<int[]> result = new ArrayList<>();
        while(i<j){
            if(sum==target){
                int[] res = new int[j-i+1];
                for(int k=i,pos=0;k<=j;k++){
                    res[pos++] = k;
                }
                result.add(res);
                sum-=i;
                i++;         
            }
            else if(sum>target){
                sum-=i;
                i++;
            }else{
                j++;
                sum+=j;
            }
        }
        return result.toArray(new int[0][]);
    }
}

 

标签:窗口,target,Offer,int,57,II,序列,滑动,sum
From: https://www.cnblogs.com/End1ess/p/17322538.html

相关文章

  • Nios II之PIO中断
    PIO中断应用Quartus软件中集成了Qsys工具,用于搭建SOPC系统,其前身是SOPCBuilder。在Qsys中有一个PIO核的组件,PIO在SOPC系统中用的非常多,LCD、按键、LED、数据采集等等都可以使用PIO组件。PIO可以在Qsys中设置外部中断。如图所示,设置5位按键,勾选边缘捕获,边沿类型为下降沿,中断类型......
  • 1040. 移动石子直到连续 II
    题目链接:1040.移动石子直到连续II方法:找规律解题思路参考—【图解】下跳棋代码classSolution{public:vector<int>numMovesStonesII(vector<int>&stones){sort(stones.begin(),stones.end());intn=stones.size();inte1=stones......
  • 剑指 Offer 64. 求1+2+…+n
    题目链接:剑指Offer64.求1+2+…+n方法:逻辑运算符短路原则解题思路例如:对于表达式\(A&&B\),若\(A\)为\(false\),那么就不会计算\(B\);代码classSolution{public:intsumNums(intn){n&&(n+=sumNums(n-1));returnn;}};复杂度......
  • 剑指 Offer 60. n个骰子的点数
    题目链接:剑指Offer60.n个骰子的点数方法:动态规划解题思路\(n=1\)时可能的和为\([1,6]\),其概率为\(dp[1][]=[1/6,1/6,1/6,1/6,1/6,1/6]\)\(n=2\)时对于第一个骰子为\(1\)时,第二个骰子可以为\([1,6]\),其可以构成的和为\([2,7]\),分别为其中的和\([i+......
  • 47. 全排列 II
    给定一个可包含重复数字的序列nums,按任意顺序返回所有不重复的全排列。输入:nums=[1,1,2]输出:[[1,1,2],[1,2,1],[2,1,1]]>我的解法classSolution{private:voidtraversal(vector<int>&nums,vector<bool>&used,intstartdex){if(startdex>nums......
  • 90. 子集 II
    给你一个整数数组nums,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。返回的解集中,子集可以按任意顺序排列。>我的解法classSolution{private:voidtraversal(vector<int>&nums,vector<bool>&used,intstartdex){i......
  • 【剑指 Offer 】14- I. 剪绳子
    【题目】给你一根长度为n的绳子,请把绳子剪成整数长度的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。示例1:输入:......
  • 【剑指 Offer】 66. 构建乘积数组
    【题目】给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B[i]的值是数组A中除了下标i以外的元素的积,即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:输入:[1,2,3,4,5]输出:[120,60,40,30,24]来源:力扣(LeetCode)链接:https://leetc......
  • 用 Go 剑指 Offer 56 - I. 数组中数字出现的次数
    一个整型数组nums里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。示例1:输入:nums=[4,1,4,6]输出:[1,6]或[6,1]示例2:输入:nums=[1,2,10,4,1,4,3,3]输出:[2,10]或[10,2]限制:2<=nums.length......
  • 用 Go 剑指 Offer 31. 栈的压入、弹出序列 (辅助栈)
    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列{1,2,3,4,5}是某栈的压栈序列,序列{4,5,3,2,1}是该压栈序列对应的一个弹出序列,但{4,3,5,1,2}就不可能是该压栈序列的弹出序列。示例1:输入:pushe......