【滑动窗口专题】剑指 Offer 57 – II. 和为s的连续正数序列-跟着帅地玩副业，开拓第二曲线PlayOffer

lQl 永久会员 2024年12月22日上午11:25

时间复杂度O(n)
空间复杂度O(1)

class Solution {
    public int[][] fileCombination(int target) {
        List<int[]> result = new ArrayList<>();
        int l = 1;
        int r = 2;
        int sum = 3;
        while (l < r) {
            if (target == sum) {
                int[] s = new int[r - l + 1];
                for (int i = l; i <= r; i++) {
                    s[i - l] = i;
                }
                result.add(s);
            }
            if (target <= sum) {
                sum -= l;
                l++;
            } else {
                r++;
                sum += r;
            }

        }
        return result.toArray(new int[0][]);
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月20日下午7:53

思路：构建滑动窗口从左向右滑动，循环中，每轮判断滑动窗口内元素和与目标值 target 的大小关系，若相等则记录结果，若大于 target 则移动左边界 i（以减小窗口内的元素和），若小于 target 则移动右边界  （以增大窗口内的元素和）。

class Solution {
    public int[][] fileCombination(int target) {
        List<int[]> resList=new ArrayList<>();
        int left=1;
        int right=1;
        int sum=1;
        while(left<=(target/2)){
            if(sum<target) {
                right++;
                sum=sum+right;
                }else if(sum>target){
                sum=sum-left;
                left++;
            }else{
                int num=0;
                int[] tmpArr=new int[right-left+1];
                for(int i=left;i<=right;i++){
                    tmpArr[num++]=i;
                }
                resList.add(tmpArr);
                sum=sum-left;
                left++;
                right++;
                sum=sum+right;
            }
        }
        return resList.toArray(new int[resList.size()][]);
    }
}
时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

陆狗陆狗普通 2024年12月18日上午1:27

解题思路
– 定义一个左闭右开的滑动窗口，[l,r)。为什么是左闭右开，因为结果sum，如果是左边右滑（sum变小），只需要sum-当前l；如果是右边右滑（sum变大），只需要sum+当前r 即可【如果是右闭，就需要先r++再去sum+r，形式上不统一】。
– 左边只能右滑（让区间变小，让值变小），右边也只能右滑（让区间变大，值变大）【禁止左滑，会让情况变得复杂】
【题解1】

class Solution {
    public int[][] fileCombination(int target) {
        // 使用滑动窗口[i,j)来遍历[1,+无穷)的数据
        // 把滑动窗口里面包含的元素作为一个子数组进行输出，把这样所有的子数组全部找到
        // 区域是从1开始的
        // 左边只能右移，让范围变小；右边只能右移让范围变大
        int l = 1;
        int r = 1;
        int sum = 0;
        List<int[]> result = new ArrayList();
        // 因为区域是无限大的，所以要用l<=target/2去限制，因为元素至少有2个，所以取一半即可
        while (l <= target / 2) {
            if (sum < target) {
                // 当前结果小于目标值，右边右移
                sum = sum + r;
                r++;
            } else if (sum > target) {
                // 当前结果大于目标值，左边右移
                sum = sum - l;
                // 【错误点1】移动方向错误
                l++;
            } else {
                // 当前结果等于目标值，结果储存后，右移（能让下一步进行右移）
                int[] tmpt = new int[r - l];
                for (int i = l; i < r; i++) {
                    tmpt[i - l] = i;
                }
                result.add(tmpt);
                // 【错误2】忘记写，导致sum不更新
                sum = sum - l;
                // 【错误3】忘记写，导致循环不能结束
                l++;

            }
        }
        return result.toArray(new int[result.size()][]);

    }
}

错误点1：移动方向错误，都只能右滑，只能l++和r++
错误点2：在相等时，把数据存储到数组后，左边就需要右滑，同时sum要减小
错误点3：在相等时，把数据存储到数组后，左边就需要右滑，同时l要增加

0 赞同 0 条回复

秋山丽奈普通 2024年12月17日下午7:25

思路：使用滑动窗口

class Solution {
    public int[][] fileCombination(int target) {

        List<int[]> ans = new ArrayList<int[]>();

        int head = 1;
        int tail = 2;
        int sum = 3;
        while(head < tail){
            if(sum == target){
                // 将当前 结果保存 
                int[] current = new int[tail-head+1];

                for(int i = head; i <= tail; i ++){
                    current[i-head] = i;
                } 

                ans.add(current);
            }

            if(sum < target){
                tail ++;
                sum += tail;
            }else if(sum >= target){
                sum -= head;
                head ++;
            }

        }

        return ans.toArray(new int[0][]);
    }
}

0 赞同 0 条回复

Jerry 普通 2024年12月16日下午11:08

class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        int left = 1, right = 1;
        int sum = 0;
        vector<vector<int>> res;
        while(right < target){
            sum += right;
            if(sum == target && left < right){
                res.push_back({left, right});
            }
            right++;
            while(sum > target && left < right){
                sum -= left;
                left++;
                if(sum == target && left < right){
                    res.push_back({left, right - 1});
                }
            }
        }
        int sz = res.size();
        vector<vector<int>> ans(sz, vector<int>());
        for(int i = 0; i < sz; i++){
            int start = res[i][0];
            int end = res[i][1];
            for(int j = start; j <= end; j++){
                ans[i].push_back(j);
            }
        }
        return ans;
    }
};

时间空间

0 赞同 0 条回复

迢迢星野普通 2024年12月16日下午6:35

class Solution {
    /**
     * 待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定
     * 数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。
     * 注意，返回时需遵循以下规则：
     *      每种组合按照文件编号 升序 排列；
     *      不同组合按照第一个文件编号 升序 排列。
     *      
     * 题意解读：和为 target 的递增子序列
     *  方法一：数学公式，求和公式
     *  方法二：滑动窗口
     * @param target
     * @return
     */
    public int[][] fileCombination(int target) {
        int l = 1, r = 2;
        int sum = 3;
        List<int[]> res = new ArrayList<>();
        while (l < r) {
            // 记录 [l, r] 之间的元素
            if (sum == target) {
                int[] ans = new int[r - l + 1];
                for (int k = l; k <= r; k++) {
                    ans[k - l] = k;
                }
                res.add(ans);
            }
            // 滑动窗口何时缩小？sum >= target 时
            if (sum >= target) {
                sum -= l;
                l++;
            } else {
                // 滑动窗口何时扩大？ sum < target
                r++;
                sum += r;
            }
        }
        return res.toArray(new int[0][]);
    }
}

思路：数学公式、滑动窗口
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

Aatorx 永久会员 2024年12月16日下午2:49

class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        vector<vector<int>> res;
        int l = 1;
        int r = 1;
        int t = target;
        while(r <= (t + 3) / 2) {
            if (target < 0) {
                target += l;
                l++;
            }
            else if (target == 0) {
                vector<int> v;
                for (int i = l; i < r; i++){
                    v.push_back(i);
                }
                res.push_back(v);
                target += l;
                l++;
            }
            else {
                target -= r;
                r++;
            }
        }
        return res;
    }
};

利用整数l，r来记录滑动窗口左右断点，若窗口内数字和大于目标，则移动左端点，若小于，则移动右端点，若相同，则记录结果。
时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

月下足迹普通 2024年12月15日上午10:56

public int[][] fileCombination(int target) {
List<List> result = new ArrayList<>();
int left = 1, right = 2; // 滑动窗口的起点和终点

    while (left < right) {
        // 计算窗口内的连续整数和
        int sum = (right - left + 1) * (left + right) / 2;

        if (sum == target) {
            // 找到符合条件的组合
            List<Integer> combination = new ArrayList<>();
            for (int i = left; i <= right; i++) {
                combination.add(i);
            }
            result.add(combination);
            left++; // 缩小窗口
        } else if (sum < target) {
            right++; // 扩大窗口
        } else {
            left++; // 缩小窗口
        }
    }

    // 将结果列表转换为二维数组
    int[][] array = new int[result.size()][];
    for (int i = 0; i < result.size(); i++) {
        List<Integer> innerList = result.get(i);
        array[i] = new int[innerList.size()];
        for (int j = 0; j < innerList.size(); j++) {
            array[i][j] = innerList.get(j); // 将 Integer 转换为 int
        }
    }
    return array;
}

0 赞同 0 条回复

晓宇普通 2024年12月14日上午11:28

// 滑动窗口
class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        int l = 1,r = 1,sum = 1;
        vector<vector<int>> res;

        while(l <= target / 2){  // 左边界大于target / 2 那么l + r相加一定大于target
            if(sum < target)
                sum += ++r;
            else if(sum > target)
                sum -= l++;
            else{
                vector<int> temp;
                for(int i = l;i <= r; i++)
                    temp.push_back(i);
                res.push_back(temp);
                sum -= l++; // 左边界右移
                sum += ++r; // 优化：有边界右移，减少循环次数

            }

        }
        return res;
    }
    // o(n) o(1)
};

0 赞同 0 条回复

jaron 普通 2024年12月14日上午8:03

class Solution {
    public int[][] fileCombination(int target) {
        List<int[]> res = new ArrayList<>();
        int l = 1, r = 2, sum = 3;
        // l > target / 2，l+r就大于target了
        while (l <= target / 2) {
            if (sum < target) {
                // l右移
                r++;
                sum += r;
            } else if (sum > target) {
                // r右移
                sum -= l;
                l++;
            } else {
                int[] temp = new int[r - l + 1];
                for (int i = 0; i < r - l + 1; i++) {
                    temp[i] = l + i;
                }
                res.add(temp);
                // l r 都右移
                sum -= l;
                l++;
                r++;
                sum += r;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月14日上午12:16

滑动窗口

class Solution {
    public int[][] fileCombination(int target) {
        int sum=0;
        int i=1;
        int j=1;
        List<int[]> res=new ArrayList<>();
        while(i<=target/2){
            if(sum<target){
                sum+=j;
                j++;
            }else if(sum>target){
                sum-=i;
                i++;
            }else {
                int[] arr=new int[j-i];
                for(int a=i;a<j;a++){
                    arr[a-i]=a;
                }
                res.add(arr);
                sum-=i;
                i++;
            }

        }
        return res.toArray(new int[res.size()][]);
    }
}

On O根号 target

0 赞同 0 条回复

苯庸普通 2024年12月13日下午7:59

class Solution {
public int[][] fileCombination(int target) {
int l = 1, r = 1;
List<int[]> list = new ArrayList();
int sum = 0;
while(r < target){
sum += r++;
while(sum > target){
sum -= l++;
}
if(sum target){
int[] res = new int[r – l];
for(int i = 0; i < res.length; i++){
res[i] = l + i;
}
list.add(res);
}
}
int[][] res = new int[list.size()][];
for(int i = 0; i < res.length; i++){
res[i] = list.get(i);
}
return res;
}
}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

【滑动窗口专题】剑指 Offer 57 – II. 和为s的连续正数序列

共以下 12 个回答

# 回答此问题取消回复

【滑动窗口专题】剑指 Offer 57 – II. 和为s的连续正数序列

共以下 12 个回答

# 回答此问题 取消回复

# 回答此问题取消回复