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

mpweixin用户普通 2024年4月2日下午4:03

public int[][] fileCombination(int target) {
int i=1;
int j=1;
int sum=0;
List<int[]> res = new ArrayList<>();
while(i<=target/2){
if(sum<target){
sum+=j;
j++;
}else if(sum>target){
sum-=i;
i++;
}else{
int[] ans =new int[j-i];
for(int k=i;k<j;k++){
ans[k-i]=k;
}
res.add(ans);
sum-=i;
i++;
}
}
return res.toArray(new int[res.size()][]);
}
思路：滑动窗口

0 赞同 0 条回复

kfaebot 普通 2024年3月29日下午4:37

class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        vector<vector<int>> res;
        int left=1; 
        int right=2;
        int sum=3;

        //开始循环
        while(left<right){
            if(sum==target){
                vector<int>tmp;
                for(int i=left;i<right+1;i++){
                    tmp.push_back(i);
                }
                res.push_back(tmp);
                sum-=left;
                left++;
            }

            if(sum<target){
                right++;
                sum+=right;
            }
            else if(sum>target){
                sum-=left;
                left++;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

方铎码农普通 2024年3月28日下午11:25

class Solution {
    public int[][] fileCombination(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][]);
    }
}

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

0 赞同 0 条回复

神经蛙普通 2024年3月27日上午12:15

class Solution {
public:
vector<vector> fileCombination(int target) {
int i = 1, j = 2, s = 3;
vector<vector> res;
while(i < j) {
if(s target) {
vector ans;
for(int k = i; k <= j; k++)
ans.push_back(k);
res.push_back(ans);
}
if(s >= target) {
s -= i;
i++;
} else {
j++;
s += j;
}
}
return res;
}
};
时间复杂度O（n）空间复杂度O(1)

0 赞同 0 条回复

Jimmy 普通 2024年3月25日下午9:10

时间复杂度O(n)

class Solution {
public:
    vector<vector<int>> fileCombination(int target) {
        if(target == 1)return {};
        vector<vector<int>> res;
        int left = 1,right = 1;
        int sum = left;//设结果区间为左闭右闭
        while(left <= target/2)
        {
            if(sum < target)
            {
                right++;//因为是右闭所以先将有边界++再与其相加
                sum += right;
            }
            else if(sum > target)
            {
                sum -= left;
                left++;
            }
            else
            {
                int i=left;
                vector<int> tmpRes;
                while(i <= right)
                {
                    tmpRes.push_back(i);
                    i++;
                }
                res.push_back(tmpRes);
                sum -= left;
                left++;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

Yox 普通 2024年3月25日下午12:19

class Solution:
def fileCombination(self, target: int) -> List[List[int]]:
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
else:
j += 1
s += j

    return res

o n o 1 空间

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月25日上午10:30

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 = sum + j;
            } else if(sum > target){
                sum = 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 = sum - i;
                i++;
                j++;
                sum = sum + j;
                res.add(temp);
            }
        }

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

时间复杂度：O(n)
额外空间复杂的：O(1)

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月25日上午8:17

打卡

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

0 赞同 0 条回复

南梁陈庆之普通 2024年3月25日上午12:36

滑动窗口

class Solution {
    public int[][] fileCombination(int target) {
        List<int[]> list = new ArrayList<>();
        int i = 1, j = 2 , s = 3;
        while (i < j) {
            if (s == target) {
                int[] ans = new int[j - i + 1];
                for (int k = i; k <= j; k++) {
                    ans[k - i] = k;
                }
                list.add(ans);
            }
            if (s >= target) {
                s = s - i;
                i++;
            } else {
                j++;
                s = s + j;
            }
        }
        return list.toArray(new int[0][]);
    }
}

0 赞同 0 条回复

云无深雁影普通 2024年3月24日下午11:40

class Solution {
public int[][] fileCombination(int target) {
List<int[]> ans = new ArrayList<>();
int begin = 1;
int end = 1;
int sum = 1;
while(begin <= end && end < target){
if(sum target){
int[] t = new int[end-begin+1];
for(int i = 0; i <= end – begin; i++)
t[i] = i + begin;
ans.add(t);
sum -= begin;
begin++;
}
else if(sum > target){
sum -= begin;
begin ++;
}
else{
end++;
sum += end;
}
}
return ans.toArray(new int[0][]);
}
}
//时间复杂度On
//空间复杂度O1

0 赞同 0 条回复

heathhou 普通 2024年3月24日下午11:02

class Solution {
public:
    vector<vector<int>> fileCombination(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> temp(j - i + 1);
                int index = 0;
                for(int k = i; k <= j; ++k){
                    temp[index++] = k;
                }
                sum -= i;
                i++;

                j++;
                sum += j;
                res.push_back(temp);
            }
        }
        return res;
    }
};

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

0 赞同 0 条回复

机电皮怪永久会员 2024年3月24日下午10:26

通过i和j作为滑动窗口,最开始没处理循环的问题
时间复杂度O(n)
空间复杂度O(1)

“`c++
class Solution {
public:
vector> fileCombination(int target) {
if(target == 0)
{
return {};
}
//通过i和j作为滑动窗口
int sum = 1;
vector> result;
for(int i = 1, j = 1; i <= target/2;) { if(sum < target) { j++; sum += j; } else if(sum > target)
{
sum -= i;
i++;
}
else
{
vector temp(j – i + 1);
for(int k = i, number = 0; k <= j; number++ ,k++) { temp[number] = k; } sum -= i; i++; j++; sum += j; result.push_back(temp); } } return result; } }; ```

0 赞同 0 条回复

mpweixin用户普通 2024年3月24日下午10:08

java
class Solution{
public int[][] fileCombination(int target){
List<int[]> vec = new ArrayList<int[]>();
int sum = 0, limit = (target – 1) / 2;
for(int i = 1; i <= limit; ++i){
for(int j = i;; ++j){
sum += j;
if(sum > target){
sum = 0;
break;
}else if(sum target){
int[] res = new int[j – i + 1];
for(int k = i; k <= j; ++k){
res[k – i] = k;
}
vec.add(res);
sum = 0;
break;
}
}
}
return vec.toArray(new int[vec.size()][]);
}
}
提交

0 赞同 0 条回复

紫芝普通 2024年3月24日下午10:07

思路：滑动窗口

func fileCombination(target int) [][]int {
    low, sum := 1, 0
    var ans [][]int
    end := target / 2 + 1
    for cur:=low; cur <= end; cur++ {
        sum += cur
        if sum > target {
            for low<=cur && sum > target {
                sum -= low
                low++
            }
        }
        if sum == target { 
            var tmp []int
            for i:=low; i<=cur; i++ {
                tmp = append(tmp, i)
            }
            ans = append(ans, tmp)
            sum -= low
            low++
        }
    }
    return ans
}

0 赞同 0 条回复

Raphtalia. 普通 2024年3月24日下午9:44

class Solution {
public:
vector<vector> fileCombination(int target) {
vector<vector> res;
vector ans;
for(int l = 1, r = 2; l < r;) {
if(target <= r) break;
int sum = (l + r) * (r – l + 1) / 2;
if(sum target) {
for(int i = l; i <= r; i ++) {
ans.push_back(i);
}
res.push_back(ans);
ans.clear();
l ++;
r ++;
}
if(sum > target) {
l ++;
}
if(sum < target) {
r ++;
}
}
return res;
}
};
时间复杂度O（n），空间复杂度O（1）

0 赞同 0 条回复

言之命至普通 2024年3月24日下午9:22

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();//保存结果
        int i = 1, j = 1;//左右指针
        int sum = 1;//初始化窗口的和
        while(i <= target/2){//左边界不会超过 target/2，因为至少含有两个数，如果左边界超过了，右边界也一定超过了，和一定不符合了
            if(sum < target){ //右边界向右一位
                j++;
                sum = sum + j;
            } else if(sum > target){//左边界向右一位
                sum = 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 = sum - i;
                i++;//左右边界都向右移一位
                j++;//这里是一个小优化，因为  sum = sum - i;  之后一定<target
                sum = sum + j;
                res.add(temp);
            }
        }

        return res.toArray(new int[res.size()][]);//转为二维数组
    }
}

0 赞同 0 条回复

王位詮釋普通 2024年3月24日下午9:09

```java
class Solution {
    public int[][] fileCombination(int target) {
        List<int[]> results = new ArrayList<>();//int[] 本身就是引用类型
        int l = 1;
        int r = 1;
        int sum = l;
        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 index = 0;
                for(int k = l;k<=r;k++){
                    temp[index++] = k;
                }
                sum-=l;
                l++;//继续往后移动
                r++;
                sum+=r;
                results.add(temp);
            }
        }
        return results.toArray(new int[results.size()][]);
    }
}
思路：我感觉这个比下一道题难，不知道怎么转换返回值类型，之前不知道java里的数组是可以有只写第一个括号里的值不写第二个括号的值。
动态改变滑动窗口的大小以及位置，如果窗口内的值为target则将序列获取，如果已经大于了target则需要将sum减去left的值，并将left和right往后移动，如果小于target的话就只移动right的值。小优化：left最多只到target/2，应为target/2后面的值是大于他的，所以后面的值与其相加一定大于target，后面的就不需要遍历了。

“`

0 赞同 0 条回复

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

共以下 17 个回答

# 回答此问题取消回复

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

共以下 17 个回答

# 回答此问题 取消回复

# 回答此问题取消回复