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

Sheng 永久会员 2023年9月19日下午3:33

        int left = 1;
        int right = 2;
        int sum = left + right;
        List<int[]> vec = new ArrayList<int[]>();
        while(left <= target/2) {//最少两个数，因此left最大值也就是target的一半
            if(sum == target) {
                //返回结果
                int[] res = new int[right - left + 1];
                for(int i = 0; i <= right - left; i++) {
                    res[i] = left + i;
                }
                vec.add(res);
            }
            if(sum < target) {
                right++;
                sum += right;//小于 的时候right右移，sum+right
            }
            else {
                sum -= left;//大于 等于 的时候left右移，sum-left，这样避免多次计算sum
                left++;
            }
        }
        return vec.toArray(new int[vec.size()][]);

0 赞同 0 条回复

sc_Yang 普通 2023年9月12日上午8:54

/*
我们用两个指针l和r表示当前枚举到的以l为起点到r的区间，sum表示[l,r]的区间和，由求和公式可求得为 sum=(l+r)×(r−l+1)2\，起始 l=1,r=2.
一共有三种情况：
如果 sum<target则说明指针 rrr 还可以向右拓展使得sum增大，此时指针r向右移动,即r+=1
如果 sum>target则说明以l为起点不存在一个r使得sum=target，此时要枚举下一个起点，指针l向右移动，即l+=1
如果 sum==target则说明我们找到了以l为起点得合法解[l,r]，我们需要将[l,r]的序列放进答案数组，且我们知道以l为起点的合法解最多只有一个，所以需要枚举下一个起点，指针l向右移动，即l+=1
终止条件即为l>=r的时候，这种情况的发生指针r移动到了⌊target2⌋+1的位置，导致l<r的时候区间和始终大于targett
*/
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> resvec;
        vector<int> curres;
        for(int l=1,r=2;l<r;){
            int sum = (l+r)*(r-l+1)/2;
            if(sum<target){
                r++;
            }else if(sum>target){
                l++;
            }else{ // sum==target,此时收集该组数字，并且改变l寻找下一符合条件的序列
                curres.clear();
                for(int i=l; i<=r; i++){
                    curres.emplace_back(i);
                }
                resvec.emplace_back(curres);
                l++;
            }
        }
        return resvec;
    }
};

0 赞同 0 条回复

sincere 普通 2023年9月10日下午9:01

思路：1、求和公式；2、滑动窗口，双指针判断区间范围和与target，小与target则右指针++，大于则左指针++，左指针大于等于右指针时结束循环
复杂度：1、时间复杂度O(n)，空间复杂度O(1)；2、时间复杂度O(n)，空间复杂度O(1)

// 求和公式
class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1;// 从1开始遍历计算左右边界i、j
        double j = 2.0;
        List<int[]> list = new ArrayList<>();
        while (i < j) {
            j = (-1 + Math.sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
            int r = (int) j;
            if (i < j && j == r) {// 只取整数
                int[] sub = new int[r - i + 1];
                for (int k = i; k <= r; k++) {
                    sub[k - i] = k;
                }
                list.add(sub);
            }
            i++;
        }
        return list.toArray(new int[0][]);
    }
}
// 滑动窗口
class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2, sum = 3;
        List<int[]> list = new ArrayList<>();
        while (i < j) {
            if (sum == target) {
                int[] tmp = new int[j - i + 1];
                for (int k = i; k <= j; k++) {
                    tmp[k - i] = k;
                }
                list.add(tmp);
            }
            // 继续向后遍历
            if (sum >= target) {
                sum -= i;
                i++;
            } else {
                j++;
                sum += j;
            }
        }
        return list.toArray(new int[0][]);
    }
}

0 赞同 0 条回复

小肸永久会员 2023年9月8日上午10:45

class Solution {
    public int[][] findContinuousSequence(int target) {
        //时间复杂度为O(target)，因为两个指针每一个最多移动(target/2 - 1)次
        //空间复杂度为O(1)
        List<int[]> res = new ArrayList<>();
        for (int l = 1, r = 2; l < r; ) {
            //等差数列求和公式
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] tmp = new int[r - l + 1];
                for (int i = l, index = 0; i <= r; i ++) {
                    tmp[index ++] = i;
                }
                res.add(tmp);
                //这里直接l++，因为r++后sum一定大于target，还是执行l++
                l ++;
            } else if (sum > target) {
                l ++;
            } else if (sum < target) {
                r ++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年9月4日下午9:32

//普通解法，一个个试
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> vec;
        int val = 1;
        while(val<(target/2+1))
        {
            vector<int> tmp;
            int sum =0;
            int num = val;
            while(sum<target)
            {
                sum+=num;
                tmp.push_back(num);
                num++;
            }
            val++;
            if(sum==target)  vec.push_back(tmp);
        }
        return vec;
    }
};
// 滑动窗口解法
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        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
            {
                vector<int> vec(j-i+1);
                int idx = 0;
                for(int k=i;k<=j;++k)
                {
                    vec[idx++]=k;
                }
                sum-=i;
                i++;
                j++;
                sum+=j;
                res.push_back(vec);
            }
        }
        return res;
    }
};

0 赞同 0 条回复

塔底的仰望永久会员 2023年9月4日下午7:10

最大的序列长度不超过2*target开根号，由于是一个等差数列以及相加等于target，可以快速算出数列的第一项以及总和
时间复杂度O(n);空间复杂度O(n)

class Solution {
    public int[][] findContinuousSequence(int target) {
        if (target == 1 || target == 2) {
            return new int[0][0];
        }
        List list = new ArrayList<>();
        int window = (int)Math.sqrt(2 * target); // 序列长度上限
        for (int i = window; i > 1; i--) {
            int[] res = new int[i];
            int mid = target / i;
            int value = mid - (i - 1) / 2;
            int sum = (2 * value + i - 1) * i / 2;
            if ( sum != target) {
                continue;
            }
            for (int j = 0; j < i; j++, value++) {
               res[j] = value;
            }
            list.add(res);
        }
        return list.toArray(new int[list.size()][]);
    }
}

0 赞同 0 条回复

JustRtn 普通 2023年9月4日下午3:32

通过通项公式：Sn=na1+n(n-1)d/2,求出a1: a1 = (Sn – n(n – 1)d / 2 ) / n，再根据n构建符合要求的数列

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        // a1 = (Sn - n(n - 1) / 2 ) / n
        vector<vector<int>> resVec;
        for (int n = sqrt(target * 2); n > 1; n--) {
            long tmp = target - n * (n - 1) / 2;
            if (tmp % n != 0) continue;
            int a1 = tmp / n;
            if (a1 <= 0) continue;
            vector<int> vec(n);
            for (int i = 0; i < n; i++) {
                vec[i] = a1++;
            }
            resVec.push_back(vec);
        }
        return resVec;
    }
};

滑动窗口法

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> resVec;
        int i = 1;
        int j = 1;
        int sum = 1;
        while (i <= target / 2) {
            if (sum < target) {
                j++;
                sum += j;
            } else if (sum > target) {
                sum -= i;
                i++;
            } else {
                vector<int> vec(j - i + 1);
                int tmp = i;
                for (int k = 0; k < vec.size(); k++) {
                    vec[k] = tmp++;
                }
                resVec.emplace_back(vec);
                sum -= i;
                i++;
                j++;
                sum += j;
            }
        }
        return resVec;
    }
};

0 赞同 0 条回复

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

共以下 7 个回答

# 回答此问题取消回复

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

共以下 7 个回答

# 回答此问题 取消回复

# 回答此问题取消回复