当前位置 博文首页 > 数据结构和算法:剑指 Offer-和为s的连续正数序列

    数据结构和算法:剑指 Offer-和为s的连续正数序列

    作者:[db:作者] 时间:2021-07-29 12:45

    截止到目前我已经写了 500多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
    下载链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
    提取码:6666

    在这里插入图片描述

    在这里插入图片描述
    视频链接
    因为至少有两个数,所以窗口的左边界left <= target / 2,题中是把找到的序列添加到列表list中,最后在转化为二维数组,来看下代码

    public int[][] findContinuousSequence(int target) {
        int left = 1; // 滑动窗口的左边界
        int right = 2; // 滑动窗口的右边界
        int sum = left + right; // 滑动窗口中数字的和
        List<int[]> res = new ArrayList<>();
        //窗口的左边是窗口内的最小数字,只能小于等于target / 2,
        //因为题中要求的是至少含有两个数
        while (left <= target / 2) {
            if (sum < target) {
                //如果窗口内的值比较小,右边界继续向右移动,
                //来扩大窗口
                sum += ++right;
            } else if (sum > target) {
                //如果窗口内的值比较大,左边边界往右移动,
                //缩小窗口
                sum -= left++;
            } else {
                //如果窗口内的值正好等于target,就把窗口内的值记录
                //下来,然后窗口的左边和右边同时往右移一步
                int[] arr = new int[right - left + 1];
                for (int k = left; k <= right; k++) {
                    arr[k - left] = k;
                }
                res.add(arr);
                //左边和右边同时往右移一位
                sum -= left++;
                sum += ++right;
            }
        }
        //把结果转化为数组
        return res.toArray(new int[res.size()][]);
    }
    

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int n = 2;
        //死循环
        while (true) {
            int total = target - n * (n - 1) / 2;
            //当分子小于等于0的时候,退出循环
            if (total <= 0)
                break;
            //如果首项是正整数,满足条件
            if (total % n == 0) {
                int[] arr = new int[n];
                //找出首项的值
                int startValue = total / n;
                for (int k = 0; k < n; k++) {
                    arr[k] = startValue + k;
                }
                res.add(arr);
            }
            //继续找
            n++;
        }
        //反转,比如当target等于9的时候,结果是
        //[[4,5],[2,3,4]],但题中要求的是不同
        // 序列按照首个数字从小到大排列,所以这里反转一下
        Collections.reverse(res);
        //把list转化为数组
        return res.toArray(new int[res.size()][]);
    }
    

    在这里插入图片描述

    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        //因为至少是两个数,所以target先减1
        target--;
        for (int n = 2; target > 0; n++) {
            //找到了一组满足条件的序列
            if (target % n == 0) {
                int[] arr = new int[n];
                //找出首项的值
                int startValue = target / n;
                for (int k = 0; k < n; k++) {
                    arr[k] = startValue + k;
                }
                res.add(arr);
            }
            target -= n;
        }
        Collections.reverse(res);
        //把list转化为数组
        return res.toArray(new int[res.size()][]);
    }
    
    cs