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

发表回复

登录后才能评论