剑指offer57-和为s的连续正数序列

原题(来源Leetcode)

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

解法

思想

这道题最大的坑就是用二维数组做返回值吧。。确实语法上挺麻烦的,解法就是滑动窗口,一个prev一个next,如果当前区间内的所有值的和小于目标值,next后移一位,如果大于目标值,prev后移一位,如果等于目标值,把当前区间内的所有数放入数组中再放入一个list中。

这样下去直到prev大于目标值的一半,就可以结束循环了,然后将list中所有的数组再搞进一个数组里去。

代码

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<int[]>();
        int prev = 1,next = 1;
        int sum = 1;
        while(next<=(target+1)/2){
            if(sum > target){
                sum = sum-prev;
                prev++;
            }else{
                if(sum == target){
                    int[] nums = new int[next-prev+1];
                    for(int i = 0;i<next-prev+1;i++){
                        nums[i] = i+prev;
                    }
                    list.add(nums);
                }
                next++;
                sum = sum+next;
            }
        }
        int[][] ans = new int[list.size()][];
        for(int i = 0;i<list.size();i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer57-%e5%92%8c%e4%b8%bas%e7%9a%84%e8%bf%9e%e7%bb%ad%e6%ad%a3%e6%95%b0%e5%ba%8f%e5%88%97/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年3月5日 23:17
下一篇 2020年3月6日 16:53

相关推荐

  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  …

    算法 2020年5月14日
    090
  • leetcode61-旋转链表

    原题 给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。 示例1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->…

    算法 2019年12月17日
    0110
  • leetcode238-除自身以外数组的乘积

    原题 给你一个长度为 n 的整数数组 nums,其中 n > 1,返回输出数组 output ,其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积…

    算法 2020年6月4日
    080
  • 程序员面试金典08.01-三步问题

    原题(来源Leetcode) 三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模…

    算法 2020年6月19日
    04560
  • 蓝桥杯试题-黑色星期五

    原题 资源限制 时间限制:1.0s 内存限制:512.0MB 问题描述  有些西方人比较迷信,如果某个月的13号正好是星期五,他们就会觉得不太吉利,用古人的说法,就是“诸事不宜”。…

    算法 2020年2月28日
    0120
  • leetcode300-最长上升子序列

    原题 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,10…

    算法 2020年3月14日
    0250
  • leetcode999-车的可用捕获量

    原题 999. 车的可用捕获量 - 力扣(LeetCode) 解法 思想 这道题题目有点难理解,其实就是上下左右搜索,质量有点低了。 代码 class Solution { cha…

    算法 2020年3月26日
    070
  • leetcode150-逆波兰表达式求值

    原题 根据逆波兰表示法,求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。 说明: 整数除法只保留整数部分。 给定逆波兰…

    2019年12月12日
    0110
  • leetcode3-无重复字符的最长子串

    原题 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长…

    2019年12月26日
    0100
  • leetcode110-平衡二叉树

    原题 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。 示例 1:  给定二叉树 […

    算法 2020年1月17日
    0170

发表回复

登录后才能评论