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

相关推荐

  • leetcode779-第K个语法符号

    原题 在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为01,1替换为10。 给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始) 例子: 输入: N…

    算法 2020年1月22日
    0110
  • leetcode350-两个数组的交集II

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例2: 输入: nums1 = …

    算法 2019年12月23日
    0400
  • 剑指offer44-数字序列中某一位的数字

    原题(来源Leetcode) 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位…

    算法 2020年6月15日
    02900
  • leetcode1160-拼写单词

    原题 给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。 假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字…

    算法 2020年3月17日
    0130
  • leetcode169-多数元素

    原题 给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例1:…

    算法 2020年2月5日
    090
  • leetcode530-二叉搜索树的最小绝对差

    原题 给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。 示例: 输入:    1    &n…

    算法 2020年2月22日
    01330
  • leetcode203-移除链表元素

    原题 删除链表中等于给定值 val 的所有节点。 示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3->4->5 解法 思想 pre指…

    算法 2019年12月16日
    0360
  • leetcode341-扁平化嵌套列表迭代器

    原题 给定一个嵌套的整型列表。设计一个迭代器,使其能够遍历这个整型列表中的所有整数。 列表中的项或者为一个整数,或者是另一个列表。 示例1: 输入: [[1,1],2,[1,1]]…

    算法 2020年1月27日
    050
  • leetcode300-最长上升子序列

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

    算法 2020年3月14日
    0250
  • leetcode28-实现strStr()

    原题 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从…

    算法 2019年11月20日
    0130

发表回复

登录后才能评论