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

Gg 普通 2023年5月5日下午9:00

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int l = 1;
        int r = 2;
        while(l < r){
            // 利用数学公式计算双指针区间的和
            int sum = (l + r) * (r - l + 1) / 2;
            if(sum == target){
                // 满足条件
                int[] curr = new int[r - l + 1];
                for(int i = l; i <= r; i ++){
                    curr[i-l] = i;
                }
                res.add(curr);
                // 满足条件也要移动指针
                l ++;
            }else if(sum < target){
                r ++;
            }else{
                l ++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月15日上午10:00

得先减去左侧指针的值，再执行left++

class Solution {
    public int[][] findContinuousSequence(int target) {
        //正数序列 连续几个数的和为target
        int left = 1;
        int right = 2;
        int sum = 3;
        List<int[]> list = new ArrayList<>();
        while(left <= target / 2){
            if(sum < target){
                right++;
                sum += right;
            }else if(sum > target){
                sum -= left;
                left++;
            }else{
                int[] temp = new int[right - left + 1];
                for(int i = left; i <= right; i++){
                    temp[i - left] = i;
                }
                list.add(temp);
                sum -= left;
                left++;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月12日下午7:09

双指针

时间复杂度：O(N)
空间复杂度：O(N)

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> ans = new LinkedList<>();

        int[] q = new int[100010];
        int hh = 0, tt = -1;

        int sum = 0;
        for (int i = 1; i < target; i++) {

            q[++tt] = i;
            sum += i;

            while (sum > target) sum -= q[hh++];

            if (hh > tt || sum < target) continue;

            int[] tmp = new int[tt - hh + 1];
            for (int j = q[hh], k = 0; j <= q[tt]; j++, k++) {
                tmp[k] = j;
            }

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

0 赞同 0 条回复

PatNick 普通 2023年1月12日下午5:44

def findContinuousSequence(target):
    i = j = 1
    res = []
    # 这里要先设出sum=1，即i=j=1的情况，这样后面在滑动窗口的时候就可以在这个sum的基础上对移动的i或j做处理而得出sum，而不需要重新在遍历ij之间的元素得到sum
    sum = 1
    # 因为至少含有两个数，当只有两个数的时候只有两个数越接近，小的那个数就越大，且不会超过target//2
    while i <= target //2:

        if sum == target:
            res.append([_ for _ in range(i,j+1)])
            j += 1
            i += 1
            sum += (j-i+1)
        elif sum > target:
            i += 1
            sum -= (i-1)

        else:
            j += 1
            sum += j
    return res

0 赞同 0 条回复

庄重普通 2023年1月6日上午8:17

// 思路：
//     1.滑动窗口的思路，是对两端边界进行不断右移，使其符合条件
//     2.但是滑动窗口中对于边界的细节要捋清
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ret;
        int i =1 ,j = 1;
        int sum = 1;
        while(i <= target/2 ){//i是从1开始，边界问题要整好是《=
            if(sum < target){//先对j++，再让sum加上J
                // j++;
                // sum += j;
                sum += ++j;
            }
            else if(sum > target){//先对sun减去i，再对i++
                // sum -= i;
                // i++;
                sum -= i++;
            }
            else{//sum == target
                vector<int> tmp;
                for(int k = i ;k <= j ;k++){
                    tmp.push_back(k);
                }
                ret.push_back(tmp);
                sum -= i;
                i++;
                j++;
                sum += j;
            }
        }
        return ret;
    }
};
// 时间复杂度O(n)
// 空间复杂度O(1)

0 赞同 0 条回复

yanshuojune 普通 2022年12月7日上午8:58

时间：O(target)
空间：O(1)

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        # 双指针：i,j,j向右移动，比较i到j之和：
        # 小于target：j+=1；等于target：保存i到j且i+=1;大于target:i+=1
        i,j = 1, 1
        res = []
        while j <= target // 2 + 1:
            sum_res = (j+i)*(j-i+1) // 2
            if sum_res < target:
                j += 1
            elif sum_res == target:
                res.append(list(range(i,j+1)))
                i += 1
            else:
                i += 1
        return res

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:30

//滑动窗口
//lo 左边界 hi 右边界
func findContinuousSequence(target int) [][]int {
    lo, hi, sum := 1, 1, 0
    ans := make([][]int,0)

    //左边界一定不能超过target/2
    for lo <= target >> 1 {

        if  sum < target {
            //和小于目标值
            sum += hi
            hi++
        } else if  sum > target {
            //和大于目标值
            sum -= lo
            lo++
        } else {
            //找到序列
            temp := make([]int,0)
            for i := lo; i < hi; i++ {
                temp = append(temp,i)
            }
            ans = append(ans,temp)
            //起点右移
            sum -= lo
            lo++
        }

    }
    return ans
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:29

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        //滑动窗口，左闭右闭
        int i= 1;//左窗口 //从1开始即可，0无意义
        int sum = 0;
        int j = 1;//右窗口
        vector<vector<int>> result;
        while(i<=target/2){ 
            if(sum>target) {
                sum-=i;
                i++;
            }else if(sum < target){
                sum+=j;
                j++;
            }else{
                vector<int> res;
                for(int k = i; k <j;k++){//左闭右开
                    res.push_back(k);
                }
                result.push_back(res);
                sum-=i;
                i++;
            }
        }
        return result;
    }
};

0 赞同 0 条回复

波波_1936 普通 2022年11月24日下午6:04

    public int[][] findContinuousSequence(int target) {
        //时间复杂度O(n)
        //空间复杂度O(1)
        int i = 1, j = 2, sum = 3;
        List<int[]> res = new ArrayList<>();
        while (i < j) {
            if (sum == target) {
                int[] arr = new int[j - i + 1];
                for (int k = i; k <= j; k++) {
                    arr[k - i] = k;
                }
                res.add(arr);
            }
            if (sum >= target) {
                //范围左边边界向右边移动
                sum -= i;
                i++;
            } else {
                //范围右边边界向右边移动
                j++;
                sum += j;
            }
        }
        return res.toArray(new int[0][]);
    }

0 赞同 0 条回复

是梦终空永久会员 2022年11月22日上午10:31

时间O(n)
空间O(1)

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int l = 1,r = 1;
        int sum = 1;
        while(l <= target/2){
            if(sum < target){
                r = r + 1;
                sum += r;
            }else if(sum > target){
                sum = sum - l;
                l++;
            }else{
                int[] arr = new int[r-l+1];
                int index = 0;
                for(int i = l;i<=r;i++){
                    arr[index++] = i;
                }
                sum -= l;
                l++;
                r++;
                sum = sum+r;
                res.add(arr);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

0 赞同 0 条回复

y 普通 2022年11月20日下午3:27

var findContinuousSequence = function(target) {
    let result = [];
    if (target <= 2) return result;
    let l = 1;
    let r = 2;
    let sum = 3;
    while (l < r) {
       if (sum === target) {
         let temp = [];
         for (let k = l; k <= r; k++) {
            temp.push(k);
         }
         result.push(temp);
       }
    //    窗口和小于target时，窗口向右扩大
       if (sum < target) {
           r++;
           sum+=r;
       } else {
        //   窗口向左缩小  
           sum-=l;
           l++;
       }
    }
    return result;

};

0 赞同 0 条回复

@ 普通 2022年11月20日上午10:49

思路：滑动窗口

class Solution {

    //我的解法
    //时间复杂度O(N^2)
    //空间复杂度 O(1)
    public int[][] findContinuousSequence(int target) {
        int len = target / 2 + 1;
        List<List<Integer>> res = new LinkedList<>();

        for (int i = 1; i < len; i++) {

            int sum = 0;

            for (int j = i; j <= len; j++) {
                sum += j;
                if (sum == target) {
                    List<Integer> list = new LinkedList<>();
                    for (int k = i; k <= j; k++) {
                        list.add(k);
                    }
                    res.add(list);
                }

                if (sum > target)
                    break;

            }

        }

        int size = res.size();
        int[][] ints = new int[size][];

        for (int i = 0; i < size; i++) {

            List<Integer> integers = res.get(i);
            ints[i] = new int[integers.size()];
            for (int j = 0; j < integers.size(); j++) {
                ints[i][j] = integers.get(j);
            }
        }


        return ints;

    }

    //大佬的解法
    //时间复杂度O(N)
    //空间复杂度 O(1)
    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while(i < j) {
            if(s == target) {
                int[] ans = new int[j - i + 1];
                for(int k = i; k <= j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            if(s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }



    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] continuousSequence = s.findContinuousSequence(9);
        System.out.println();
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年11月20日上午9:46

class Solution {
    public int[][] findContinuousSequence(int target) {
        //这个target
        List<int[]> list = new ArrayList<>();
        int i = 1,j = 1;
        int sum = 1;
        while(i <= target/2){
            if (sum<target){
                j++;
                sum += j;
            }else if(sum > target){
                sum -= i;
                i++;
            //目标值相等的情况下
            }else{
                int [] temp = new int[j-i+1];
                int index = 0;
                for(int k = i;k <= j;k++){
                    temp [index++] = k;
                }
                sum -= i;
                i++;
                j++;
                sum += j;
                list.add(temp);
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

0 赞同 0 条回复

lobort 普通 2022年11月19日下午6:31

class Solution {
    public int[][] findContinuousSequence(int target) {
        //滑动窗口  
        List<int[]> res = new ArrayList<>();
        int left = 1, right = 1, sum = 0;
        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 k = left; k < right; k++){
                    arr[k - left] = k;
                }
                res.add(arr);
                sum -= left;
                left ++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

感觉滑动窗口和二分法差不太多

0 赞同 0 条回复

天然普通 2022年11月18日下午11:50

滑动窗口，
时间复杂度O(target)空间复杂度O(1)

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        left,right,sum ,lst = 1,2,3,[]
        while left < right:
            if sum == target:
                lst.append(list(range(left,right+1)))
            if sum >= target:
                sum -=left
                left +=1
            else:
                right +=1
                sum +=right

        return lst

0 赞同 0 条回复

派大星普通 2022年11月17日下午10:14

class Solution {
//使用滑动窗口的方法，从一开始不断向右递增，找到第一个大于S的位置,然后左边界缩小,直至到<= target/2
//时间复杂度O(n)
//空间复杂度O(1)
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int l = 1;
        int r = 1;
        int sum = 1;

        while(l <= target/2){
            if(sum < target){
                r++;
                sum += r;
            }else if (sum > target) {
                sum -= l;
                l++;
            }else {
                int[] temp = new int[r - l + 1];
                int t = l;
                for (int i = 0; i < r - l + 1; i++) {
                    temp[i] = t;
                    t++;
                }
                list.add(temp);
                sum -= l;
                l++;
                r++;
                sum += r;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月16日下午11:26

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

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        /**
        滑动窗口
        l 为窗口左边界，r 为窗口右边界，窗口中的值一定是连续值
        sum > target l右移
        sum < targer r右移
         */
        //优化边界条件
        for(int l = 1,r = 1,sum = 0;r <= (target+1)/2;r++){
            sum += r;
            //当sum大于目标值时，窗口不断收缩
            while(sum > target){
                sum -= l++;
            }
            if(sum == target){
                int[] temp = new int[r -l + 1];
                for(int i = 0;i < temp.length;i++){
                    temp[i] = l + i;
                }
                list.add(temp);
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

0 赞同 0 条回复

T 普通 2022年11月16日下午4:40

class Solution {
    public int[][] findContinuousSequence(int target) {
        int l = 1, r = 1;
        int sum = 0;
        List<int[]> res = new ArrayList<>();
        while(l <= (target / 2)) {
            // 总和小于target 滑动窗口右边界向右移动
            // 大于targe 滑动窗口左边界右移动
            if(sum < target) {
                sum += r;
                r++;
            } else if(sum > target) {
                sum -= l;
                l++;
            } else {
                int[] tmp = new int[r - l];
                for(int i = l; i < r; i++) {
                    tmp[i - l] = i;
                }
                res.add(tmp);
                sum -= l;
                l++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月16日下午3:48

时间复杂度为O（n），空间复杂度为O（1）

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int i = 1,j = 1,sum = 1;
        while(i <= target/2){
            if(sum < target){
                j++;
                sum += j;
            }else if(sum > target){
                sum -= i;
                i++;
            }else{

                int[] res = new int[j - i + 1];
                int index = 0;
                for(int k = i;k <= j;k++){
                    res[index++] = k;
                }
                sum -= i;
                i++;
                j++;
                sum += j;
                list.add(res);
            }
        }
        return list.toArray(new int[list.size()][]);

    }
}

0 赞同 0 条回复

易水寒永久会员 2022年11月16日下午3:15

List的用法

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList();
        int l = 1, r = 1;
        int sum = 0;
        for(int i = 1; i < target; i++) {
            sum += i;
            while(sum > target) {
                sum -= l;
                l++;
            }
            if(sum == target) {
                int[] t = new int[r-l+1];
                int idx = 0;
                for (int j = l; j <= r; j++) {
                    t[idx++] = j;
                }
                res.add(t);
            }
            r++;
        }
        return res.toArray(new int[res.size()][]);
    }
}

0 赞同 0 条回复

just 普通 2022年11月16日上午10:01

//相当典型的滑动窗口问题
class Solution {
public:
vector<vector> findContinuousSequence(int target) {
vector<vector> res;
vector path;
int sum=1;
int l=1;
path.push_back(1);
for(int r=2;r<=target;++r){
sum+=r;
path.push_back(r);
while(l<r&&sum>target){
sum-=(l++);
path.erase(path.begin()+0);
}
if(path.size()>1&&sumtarget) res.push_back(path);
}
return res;

};

0 赞同 0 条回复

So 普通 2022年11月16日上午9:57

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int i = 1, j = 1;
        int sum = 1;
        while (i <= target / 2) {
            if (sum < target) {
                j++;
                sum += j;
            } else if (sum > target) {
                sum -= i;
                i++;
            } else {
                int[] temp = new int[j - i + 1];
                int index = 0;
                for (int k = i; k <= j; k++) {
                    temp[index++] = k;
                }
                sum -= i;
                i++;
                j++;
                sum += j;
                res.add(temp);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

时间：O(target)，空间：O(1)

0 赞同 0 条回复

云雾里普通 2022年11月15日下午11:57

class Solution {
//滑动窗口
    public int[][] findContinuousSequence(int target) {
        int i=1,j=1;
        int sum=0;
        ArrayList<int[]> ints = 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 k = i; k < j; k++) {
                    arr[k-i]=k;
                }
                ints.add(arr);
                sum-=i+i+1;
                i+=2;
            }
        }
       return ints.toArray(new int[ints.size()][]);
    }
}

0 赞同 0 条回复

Error 普通 2022年11月15日下午10:27

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        # i左边界 j 有边界  s和 res结果
        i, j, s, res = 1, 2, 3, []
        while i < j:
            if s == target:
                res.append(list(range(i, j + 1)))
            if s >= target:
                s -= i
                i += 1
            if s < target:
                j += 1
                s += j
        return res

时间复杂度 O(logn)

0 赞同 0 条回复

青木普通 2022年11月15日下午9:23

/**
    最先想到的是从最右边的值开始迭代，如果小于target则left往左，反之right往左
    但是存的时候需要指定位置，可能这样会稍微慢一点...？

    时间O(n) 有点难想...
    空间O(l) l为答案中最长的数组长度

ps:其实这个代码有点小问题，但是却过了，
因为测试用例没有用target=1，
我之前读题忽略了正整数这个限制，
所以正确的应该是left>0
 */

class Solution {
    public int[][] findContinuousSequence(int target) {
        List list = new ArrayList();

        int right = (target - 1) / 2 + 1;
        int left = right - 1;
        while(left >= 0){
            int sum = (right - left + 1) * (left + right) / 2;
            if(sum == target){
                int[] temp = new int[right-left+1];
                for(int i=left; i<=right; i++){
                    temp[i-left] = i;
                }
                list.add(0, temp);
                left--;
                right--;
            }
            else if(sum < target){
                left--;
            }
            else{
                right--;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

0 赞同 0 条回复

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

共以下 25 个回答

双指针

# 回答此问题取消回复

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

共以下 25 个回答

双指针

# 回答此问题 取消回复

# 回答此问题取消回复