剑指 Offer 第57-2题:和为s的连续正数序列

2022-08-09  本文已影响0人  放开那个BUG

1、前言

题目描述

2、思路

本题使用滑动窗口来着,如果满足窗口里的值则停止并记录,否则则滑动。

3、代码

class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1, right = 1, sum = 0;
        List<int[]> res = new ArrayList<>();

        // 至少有两个数,左窗口超过一般就不可能有和为 target 的数,提前结束(也可以不加)
        while(left <= target / 2){
            if(sum < target){
                sum += right;
                right++;
            }else if(sum > target){
                sum -= left;
                left++;
            }else {
                int[] arr = new int[right - left];
                for(int i = left; i < right; i++){
                    arr[i - left] = i;
                }
                res.add(arr);

                // 左边界向右边移动
                sum -= left;
                left++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}
上一篇 下一篇

猜你喜欢

热点阅读