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

幽小皮永久会员 2024年3月30日下午6:47

//代码 class Solution { public int[][] fileCombination(int target) { if(target <span class="text-highlighted-inline" style="background-color: #fffd38;"> 0){ return null; } int l = 1, r = 1; List<int[]> res = new ArrayList<>(); int s = 0; while(r < target){ s += r; while(s >= target){ if(s </span> target){ int[] arr = new int[r - l + 1]; for(int j = l; j <= r; j++){ arr[j - l] = j; } res.add(arr); } s -= l; l++; } r++; } return res.toArray(new int[res.size()][]); } }

0 赞同 0 条回复

重明鸟永久会员 2023年10月15日下午8:52

// 代码
class Solution {
    public int[][] fileCombination(int target) {
        int l = 1;
        int r = 1;
        int sum = 0;
        List<int[]> result = new ArrayList<>();
        while(r < target) {
            sum += r;
            while(sum > target) {
                sum -= l;
                l++;
            }
            if(sum == target) {
                int len = r-l+1;
                int[] array = new int[len];
                for(int i=0; i<len; i++) {
                    array[i] = l+i;
                }
                result.add(array);
            }
            r++;
        }
        return result.toArray(new int[result.size()][]);
    }
}

1 赞同 0 条回复

DataSpace 普通 2023年9月25日下午5:41

“`python代码
class Solution:
def fileCombination(self, target: int) -> List[List[int]]:
if target<=0: return -1

    i,j,s,r = 1,2,3,[]
    while i<j:
        if s == target:
            r.append(list(range(i, j + 1)))
        if s>=target:
            s = s - i
            i = i + 1
        else:
            j = j + 1
            s = s + j
    return r

“`

0 赞同 0 条回复

中国用户永久会员 2023年9月13日下午3:25

”’class Solution {
public int[][] findContinuousSequence(int target) {
int l = 1, r = 2; // 初始化左右边界，构成初始序列 [1, 2]
int sum = 3; // 初始化当前序列的和为 3
List<int[]> list = new ArrayList<>(); // 用于存储符合条件的序列

    while (l < r) {             // 只要左边界小于右边界，继续循环
        if (sum == target) {    // 如果当前序列的和等于目标值
            int[] ans = new int[r - l + 1]; // 创建一个数组，用于存储当前连续整数序列
            for (int i = l; i <= r; i++) {
                ans[i - l] = i; // 填充当前连续整数序列的值到数组
            }
            list.add(ans); // 将当前符合条件的序列添加到列表中
        }
        if (sum > target) {     // 如果当前序列的和大于目标值
            sum -= l;           // 移除左边界的值，减小序列的和
            l++;                // 移动左边界
        } else {
            r++;                // 如果当前序列的和小于目标值，增加右边界的值，增加序列的和
            sum += r;
        }
    }

    return list.toArray(new int[0][]); // 将存储的符合条件的序列转换为二维数组并返回
}

}
”’java

0 赞同 0 条回复

泡芙永久会员 2023年8月30日下午12:29

class Solution {
    public int[][] findContinuousSequence(int target) {
        int i = 1, j = 2;
        int sum = 3;
        // 结果序列
        List<int[]> res = new ArrayList<>();
        while (i < j) {
            if (sum == target) {
                // 记录连续整数序列
                int[] len = new int[j - i + 1];
                for (int k = i; k <= j; k ++) {
                    len[k - i] = k;
                }
                res.add(len);
            }
            if (sum >= target) {
                sum -= i;
                i ++;
            } else {
                j ++;
                sum += j;
            }
        }
        return res.toArray(new int[0][]);
    }
}

0 赞同 0 条回复

Thaddeus 永久会员 2023年8月24日下午4:06

打卡

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        int l = 1;
        int sum = 0;
        for(int r = 1; r <= target / 2 + 1; r++){
            sum += r;
            while(sum > target){ //当sum > 目标数时，减去窗口左侧的数，直到sum <= 目标数
                sum -= l;
                l++;
            }
            if(sum == target){ //当sum = 目标数时，收集一个答案，并且减去窗口左侧那一个数使得sum < 目标数
                vector<int> v;
                for(int i = l; i <= r; i++) v.push_back(i);
                res.push_back(v);
                sum -= l;
                l++;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

阿尚普通 2023年8月16日上午11:38

//滑动窗口
class Solution {
    public int[][] findContinuousSequence(int target) {
        int j = 1;
        int sum = 0;
        ArrayList<int[]> list = new ArrayList<>();
        for(int i = 1; i <= target / 2 + 1; i++){
            sum += i;
            while(sum >= target){
                if(sum == target){
                    int[] arr = new int[i - j + 1];
                    for(int k = j; k <= i; k++){
                        arr[k - j] = k;
                    }
                    list.add(arr);
                }
                sum -= j;
                j++;
            }
        }

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

0 赞同 0 条回复

3_🔥 永久会员 2023年7月9日下午5:17

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

滑动窗口

0 赞同 0 条回复

Mr.肖永久会员 2023年7月3日下午11:10

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> a = new ArrayList<>();
        int l=1,r=1;
        int sum = l;
        while(r < target){
            while(sum != target){
                if(sum < target){
                     r++;
                     sum += r;
                }else{
                     sum -= l;
                     l++;
                }
            }
            int[] temp = new int[r-l+1];
            for(int b=l,t=0;b<=r;b++){
                temp[t++] = b;
            }
            if(temp.length >=2){
                a.add(temp);
                sum -= l;
                l++;
            }

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

    }
}

0 赞同 2 条回复

Mr.肖永久会员 @ Mr.肖 2023年7月5日下午2:53

这道题的 r < target 这个条件还有继续优化

登录以回复

Mr.肖永久会员 @ Mr.肖 2023年7月5日下午3:01

r > target/2的时候，此时连续序列加起来是大于target的，因此，r移动到(target/2+1)就可以了（+1是为了照顾target是奇数的时候），不用遍历到底，减小时间消耗。
不用嵌套while（sum != target）这个循环，加了这个以后，r的变化不能及时被最外层循环检测到，会出现最后退出最外层循环的时候sum里加了不合法的r。（这也是代码中对temp的长度进行判断的原因），这个循环是多余的。要去掉。
更新后的代码：

class Solution {
    public static int[][] findContinuousSequence(int target) {
        /**思路
         滑动窗口
         sum < target  移动右边界
         sum > target  移动左边界
         sum = targrt  保存当前数组，移动左边界，寻找下一个满足要求的数组

         注意
         避免右边界移动到target，否则会将{target}存入，不符和“至少含有两个数”题意
         */

        int l = 1, r = 1;
        int sum = l;
        List<int[]> list = new ArrayList<>();
        while (r <= (target/2+1)) {

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

KEV 永久会员 2023年6月2日下午11:08

C++版本：

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int sum=3;
        vector<vector<int>> ans;
        int i=1,j=2;
        while(i<j){
            if(sum==target){     
                vector<int> v;
                for(int k=i;k<=j;k++){
                    v.push_back(k);
                }
                ans.push_back(v);
            }
            if(sum>=target){
                sum-=i;
                i++;
            }else{
                j++;
                sum+=j;
            }
        }
        return ans;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年5月23日上午12:13

打卡

public int[][] findContinuousSequence2(int target) {
        int left = 1;
        int right = 1;
        int sum = 0;
        List<int[]> result = new ArrayList<>();

        while(left <= target / 2){

            if(sum < target){
                sum = sum + right;
                right++;
            } else if (sum > target) {
                sum = sum - left;
                left++;
            }else{
                int[] temp = new int[right - left];
                for(int i = left;i < right;i++){
                    temp[i -left ] = i;
                }
                result.add(temp);
                sum = sum - left;
                left++;
            }
        }

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

    }

0 赞同 0 条回复

LicodeCO.LTDao 普通 2023年5月6日下午6:16

function findContinuousSequence(target: number): number[][] {
    // 定义返回数组
    let res = []

    // 因为至少要含有两个数
    if(target <= 2) return res

    // target从1开始
    let l = 1
    let r = 1
    let sum = 1

    while(l <= target / 2) {
        if (sum === target) {
            let temp = []
            for(let i = l; i <= r; i++) {
                temp.push(i)
            }
            res.push(temp)
        }
        if (sum < target) {
            r++
            sum += r
        } else {
            sum -= l
            l++
        }
    }

    return res
};

0 赞同 0 条回复

Violet 永久会员 2023年4月27日下午12:34

滑动窗口

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年4月23日下午4:29

滑动窗口
class Solution {
public int[][] findContinuousSequence(int target) {

List<int> res =new Arraylist<>();
int l = 1;
int r = 2;
int sum = l + r;

while (l < r){
    if (sum = target){
        int arr[] = 
        for (int i = l ; l <= r; i++){
             arr[i - l] = i;
        }
    } else if (sum < target){
        r++;
        sum = sum + r;

    } else (sum > target){
        sum = sum - l;
        l++;
    }
}
return res.toArray(new int[res.size()][]);
}

}

0 赞同 0 条回复

席永久会员 2023年4月18日下午5:56

class Solution{
    public int[][] findContinuousSequence(int target) {
        ArrayList<int []> res = new ArrayList<>();  //创建一个ArrayList用来存储返回的数组
        int i =1; //左边界
        int j =1; //右边界
        int sum = 0; //窗口内数字的和
        int index = target / 2;
        while (i <= index){ //题目要求至少两个数相加为target，因此左边界最多到target/2为止即可
             if(sum <target){ //右边界向右移动
                 sum+=j;
                 j++;
             }else if (sum>target){  //左边界向右移动
                 sum-=i;
                 i++;
             }else{  //如果sum==target
                 int[]arr = new int [j-i];
                 for (int k = i; k < j; k++) {
                     arr[k-i]=k;
                 }
                 res.add(arr);
                 //左边界向右移动
                 sum-=i;
                 i++;
             }
        }
        return res.toArray(new int[res.size()][]);
    }
}

0 赞同 0 条回复

毛头小子永久会员 2023年4月17日下午5:09

public int[][] findContinuousSequence(int target) {
        int l = 1;
        int sum = 0;
        List<int[]> list = new ArrayList<>();//其实它也是个二维数组
        for(int r = 1 ; r < target ; r++){
            sum = sum + r;
            while(sum > target){
                sum = sum - l;
                l++;
            }
            if(sum < target){//if要放在while外面，因为有直接不用减i就等于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 条回复

小肸永久会员 2023年4月13日下午7:45

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

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

0 赞同 0 条回复

宁永久会员 2023年4月11日下午8:08

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

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 条回复

灼华永久会员 2023年4月10日下午10:01

//滑动窗口
    public int[][] findContinuousSequence(int target) {
        if(target < 1 || target > 100000) return null;
        List<int[]> ans = new ArrayList<int[]>();
        int sum=0;
        int[] tmp;
        for (int l = 1, r = 2; l < r;) {
            sum = (l + r) * (r - l + 1) / 2;//因为题中为连续正整数求和
            if (sum == target) {
                //赋值给tmp
                tmp = new int[r - l + 1];
                for (int i = l; i <= r; ++i) {
                    tmp[i - l] = i;
                }
                //添加
                ans.add(tmp);
                l++;
            } else if (sum < target)  r++;
            else l++;

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

0 赞同 0 条回复

庄重普通 2023年4月10日下午4:17

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {

        vector<int> v;
        vector<vector<int>> ret;

        int l = 1, r = 1;
        int sum = 0;
        while(r < target) {

            sum += r;
            while(sum > target) {
                sum -= l;
                l++;
            }

            if(sum == target) {

                for(int i = l; i <= r; i++){
                    v.push_back(i);
                }
                ret.push_back(v);
                v.clear();
            }
            r++; 
        }
        return ret;
    }
};
// 时间复杂度O(n)
// 空间复杂度O(1)

0 赞同 0 条回复

Only You!(^-^(^-^)) 永久会员 2023年4月9日下午8:59

/*滑动窗口
    * 时间复杂度O(target) 空间复杂度O(1)*/
    public int[][] findContinuousSequence(int target) {
        List<int[]> ans = new ArrayList<int[]>();
        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; i <= r; ++i) {
                    tmp[i - l] = i;
                }
                ans.add(tmp);
                l++;
            } else if (sum < target) {
                r++;
            } else {
                l++;
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }

0 赞同 0 条回复

Yangon 普通 2023年4月8日下午5:18

滑动窗口
class Solution {
    public int[][] findContinuousSequence(int target) {
        if(target == 0){
            return null;
        }
        List list = new ArrayList<>();

        int l = 1 ,r = 1, sum = 0;
        while(r < target){   
            sum += r;       
            while(sum > target){
                sum -= l;
                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);
            }r++;
        }
        int[][] res = new int[list.size()][];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

0 赞同 0 条回复

Bryce 普通 2023年4月7日下午9:59

滑动窗口，时间复杂度O(n)

“`gofunc findContinuousSequence(target int) [][]int {
l, r := 1,1
sum := 0
ans := make([][]int, 0)

for l <= target / 2 {
    if sum < target {
        sum += r
        r++
    } else if sum > target {
        sum -= l
        l++
    } else {
        tmp := make([]int, 0)
        for i := l; i < r;i++ {
            tmp = append(tmp, i)
        }
        ans = append(ans,tmp)
        sum -= l
        l++
    }
}    
return ans

}

“`

0 赞同 0 条回复

秊永久会员 2023年4月7日下午9:52

时间复杂度：$O(n)$

    public int[][] findContinuousSequence(int target) {
        int sum = 0;
        List<int[]> res = new LinkedList<>();


        for (int l = 1, r = 1; r < target; ++r) {
            // 右边滑入窗口；
            sum += r;

            // while(不符合条件) 左边滑出窗口；
            while (sum > target) {
                sum -= l;
                ++l;
            }

            // 满足条件，记录
            if (sum == target) {
                int[] tmp = new int[r - l + 1];
                for (int i = 0; i < r - l + 1; ++i) {
                    tmp[i] = l + i;
                }
                res.add(tmp);
            }
        }

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

0 赞同 0 条回复

是梦终空永久会员 2023年4月7日下午12:49

时间复杂度O(n)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = Integer.MAX_VALUE;    //定义为最大值
        int l = 0;int r = 0;
        int sum = 0;
        while(r < nums.length){            //判断右指针位置
            sum += nums[r];                 //给sum加右指针的数据
            while(sum >= target){           //判断sum是否大于target
                sum-=nums[l];               // 因为要得到 最短的 连续 子序列，所以这里只要sum减去最左边的， 那么子序列就在变短，
                len = Math.min(len,r-l+1);  //得到比较短的长度， 
                l++;                        //左指针右移
            }
            r++;                             //右指针右移
        }
        return len == Integer.MAX_VALUE ? 0:len; //判断是否有结果，没有就返回0;
    }
}

0 赞同 0 条回复

C++小将永久会员 2023年4月6日下午11:15

作业三打卡

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<int> temp;
        vector<vector<int>> res;
        for(int i = 1, j = 2; i <= target / 2;){
            int sum = (i + j) * (j - i + 1) / 2;
            if(sum == target){
                for(int n = i; n <= j; ++n){
                    temp.emplace_back(n);
                }
                res.emplace_back(temp);
                temp.clear();
                ++i;
            }else if(sum < target){
                ++j;
            }else{
                ++i;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

易水寒永久会员 2023年4月6日下午7:16

双指针

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

0 赞同 0 条回复

mpweixin用户普通 2023年4月6日下午6:53

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

      List<int[]> nums=new ArrayList<>();
      int left=1;
      int right=1;
      int length=0;
      int sum=0;
      while(right<target){
           sum+=right;
        while(sum>target){
            sum-=left++;//只要大于target就要缩减左边的范围
        }
           if(sum==target){
               int[] temp=new int[right-left+1];
               for(int i=0;i<temp.length;i++){
                   temp[i]=left+i;
               }
               nums.add(temp);
           }
           right++;
      }
      int [][] numx =new int [nums.size()][];
      for(int i=0;i<numx.length;i++)
      numx[i] =nums.get(i);
      return numx;
    }

}

0 赞同 0 条回复

Everglow 永久会员 2023年4月6日下午1:23

class Solution {
    public int[][] findContinuousSequence(int target) {
//窗口区间为[l, r)
//每轮外层循环处理r指向的位置
//如果窗口内的数字大于target则l向右移动直到和小于等于target
//等于target时窗口内的数字就是一个解
//如果窗口内的数字和小于target则r向右移动
        List<int[]> list = new ArrayList<>();
        int l = 1, r = 1;
        int sum = 0;
        while(r < target) {
            sum += r;
            while(sum > target) {
                sum -= l;
                l++;
            }
            if(sum == target) {
                int[] n = new int[r - l + 1];
                for(int i = 0; i < n.length; i++) {
                    n[i] = l + i;
                }
                list.add(n);
            }
            r++;
        }
        return list.toArray(new int[list.size()][]);
    }
}

0 赞同 0 条回复

菜心永久会员 2023年4月6日上午9:13

class Solution {//中文
    public int[][] findContinuousSequence(int target) {
        List<int[]> res = new ArrayList<>();
        int l = 1, r = 1;
        int sum = 0;

        while(r <= target/2 + 1) {
            sum += r;
            while(sum > target) {
                sum -= l;
                l++;
            }
            if(sum == target) {
                int[] arr = new int[r - l + 1];
                for(int k = l; k <= r; k++) {
                    arr[k-l] = k;
                }
                res.add(arr);
                sum -= l;
                l++;
            }
            r++;
        }

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

0 赞同 0 条回复

代码不会敲永久会员 2023年4月6日上午12:47

class Solution {
// 中文
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int l = 1, r = 1, s = 0;
        while (r <= target/2 + 1){
            s += r;
            while (s > target){
                s -= l;
                l++;
            }
            if (s == target){
                int[] res = new int[r-l+1];
                int cnt = 0;
                for (int i = l; i <= r; i++)    res[cnt++] = i;
                list.add(res);
            }
            r++;
        }
        // int [][] res = new int[list.size()][];
        // for (int i = 0; i < res.length; i++)    res[i] = list.get(i);
        // return res;
        return list.toArray(new int[list.size()][]);
    }
}

0 赞同 0 条回复

Kloro 永久会员 2023年4月5日下午10:16

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

        for (int l = 1, r = 1, sum = 0; r < target; r++) {
            sum += r;
            while (sum > target) {
                sum -= l;
                l++;
            }
            if (sum == target) {
                int[] temp = new int[r - l + 1];
                for (int i = 0; i < temp.length; i++) {
                    temp[i] = i + l;
                }
                list.add(temp);
            }
        }
//组装
        int[][] res = new int[list.size()][];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

0 赞同 0 条回复

【作业3】剑指 Offer 57 – II. 和为s的连续正数序列

共以下 32 个回答

打卡

作业三打卡

# 回答此问题取消回复

【作业3】剑指 Offer 57 – II. 和为s的连续正数序列

共以下 32 个回答

打卡

作业三打卡

# 回答此问题 取消回复

# 回答此问题取消回复