九号球普通 2023年11月25日上午9:50

“`java
暴力
class Solution {
public int[][] fileCombination(int target) {
List list = new ArrayList<>();
int limit = (target – 1)/2;
for (int i = 1; i <= limit; i ++) { int sum = i; int j = i+1; while (sum < target) { sum += j++; } if (sum == target) { int[] arr = new int[j - i]; for (int k = i; k < j; k++) { arr[k - i] = k; } list.add(arr); } } int[][] res = new int[list.size()][]; for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; } }

0 赞同 0 条回复

招舟子普通 2023年9月7日下午9:17

class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> list = 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 t = 0;
int[]tmp = new int[j-i+1];
for(int k=i;k<=j;k++){
tmp[t]= k;
t++;
}
list.add(tmp);
sum= sum-i;
i++;
j++;
sum=sum+j;
}
}
return list.toArray(new int[list.size()][]);
}
}
双指针思想

0 赞同 0 条回复

jhfuture 普通 2023年8月27日上午11:49

“`java
class Solution {
public int[][] findContinuousSequence(int target) {
int i=1;
int j=2;
int s=3;
List res=new ArrayList<>();
while(i} if(s>=target){ s-=i; i++; }else if(s<target){ j++; s+=j; } } return res.toArray(new int[0][]); }

}

0 赞同 0 条回复

桀桀桀Jay 普通 2023年8月3日上午9:29

java
class Solution {
    public int[][] findContinuousSequence(int target) {
        //首先i,j定义左右边界，sum小于target时j右移，大于时i右移，等于时记录下i到j，然后右移
        //作为一定程度上的优化，等于时i可以右移2位
        if(target < 3) {
            return null;
        }
        int i = 1, 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[] arr = new int[j-i];  //储存有效数组
                for(int k = 0; k < j - i; k++) {
                    arr[k] = k + i;
                }
                res.add(arr);
                sum = sum - i - (i+1);
                i += 2;
            }
        }

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

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

0 赞同 0 条回复

屠龙手段普通 2023年7月24日下午12:41

双指针，时间复杂度O(n) 空间复杂度O(1)

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

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:36

“`C++
vector> findContinuousSequence(int target) {
vector> result;

int left = 1;
int right = 2;
int sum = 3; // 初始左右两个数的和

while (left < right && left <= target / 2) {
    if (sum == target) {
        std::vector<int> sequence;
        for (int i = left; i <= right; i++) {
            sequence.push_back(i);
        }
        result.push_back(sequence);
        sum -= left; // 左边界右移，更新和
        left++;
    } else if (sum < target) {
        right++;
        sum += right; // 右边界右移，更新和
    } else {
        sum -= left; // 左边界右移，更新和
        left++;
    }
}

return result;

}

“`

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月17日下午9:50

滑动窗口

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

0 赞同 0 条回复

江畅普通 2023年7月16日下午2:43

// 和为s的连续正数序列
// 时间复杂度 O(N)
// 空间复杂度 O(1)
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int i = 1;
        int j = 2;
        int sum = 3;

        vector<vector<int>> res;
        while (i < j) {
            if (sum == target) {
                vector<int> ans;
                for (int k = i; k <= j; ++k) { ans.push_back(k); }
                res.push_back(ans);
            }
            if (sum >= target) {
                sum -= i;
                ++i;
            }
            else {
                ++j;
                sum += j;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月16日上午6:06

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        i, j = 1, 1
        curSum = 1
        res = []

        while i <= target // 2:
            if curSum < target:
                j += 1
                curSum += j
            elif curSum > target:
                curSum -= i
                i += 1
            else:
                tmp = list(range(i, j + 1))
                curSum -= i
                i += 1
                j += 1
                curSum += j
                res.append(tmp)

        return res

记得每种情况都要更新指针

0 赞同 0 条回复

WhyNot 普通 2023年7月15日下午10:49

int **findContinuousSequence(int target, int *returnSize, int **returnColumnSizes)
{
    int **res;
    int *col;
    int x = 1, y = 2;
    int limit = target / 2;
    int sum;
    int m = 0;

    res = (int **)malloc(sizeof(int *) * target);
    col = (int *)malloc(sizeof(int) * target);

    sum = x + y;
    while (x <= limit)
    {
        if (sum < target)
        {
            y++;
            sum += y;
        }
        else if (sum > target)
        {
            sum -= x;
            x++;
        }
        else
        {
            col[m] = y - x + 1;
            res[m] = (int *)malloc(sizeof(int) * col[m]);
            for (int i = 0; i < col[m]; i++)
                res[m][i] = i + x;
            m++;
            sum -= x;
            x++;
        }
    }

    *returnSize = m;
    *returnColumnSizes = col;
    return res;
}

时间复杂度为O(target)，空间复杂度为O(target)。

0 赞同 0 条回复

BOZ 普通 2023年7月15日下午8:21

【思路】利用滑动窗口完成
【复杂度】时间O(n)，空间O(1)

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> result;
        int i = 1, j = 1, sum = 1;
        while(j <= (target + 1) / 2) {
            // move i or j
            if (sum >= target) sum -= i++;
            else if (sum < target) sum += ++j;
            // record
            if (sum == target) {
                vector<int> list(j - i + 1);
                for (int k = i; k <= j; k++) list[k - i] = k;
                result.push_back(list);
            }
        }
        return result;
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月15日上午11:30

双指针+前缀和
时间：O(n)
空间：O(n)

class Solution {
    public int[][] findContinuousSequence(int target) {
        int[] sum = new int[((target + 1) >> 1) + 1];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = sum[i - 1] + i;
        }
        List<int[]> ans = new ArrayList<>();
        int left = 0, right = 2;
        while (right < sum.length) {
            int temp = sum[right] - sum[left];
            if (temp == target) {
                int[] s = new int[right - left];
                for (int i = 0; i < right - left; i++) {
                    s[i] = i + left + 1;
                }
                ans.add(s);
                right++;
            } else if (temp < target) {
                right++;
            } else {
                left++;
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

双指针+数学优化
时间：O(target)
空间：O(1)

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

0 赞同 0 条回复

行动派小彩笔普通 2023年7月13日下午4:56

//时间复杂度O(n),空间复杂度O(1) 没有使用额外的空间
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
           vector<vector<int>> ans;
           int i = 1,j = 1;
           int sum = 1;
           while(i<=target/2) //因为target至少有两位值组成，所以i不能大于target的1/2
           {
               if(sum<target) 
               {
                   j++;
                   sum+=j;
               }
               else if(sum>target)
               {
                   sum-=i;
                   i++;
               }
               else  //sum == target
               {
                   vector<int> tmp(j-i+1);
                   int idx = 0;
                   for(int k = i;k<=j;++k)
                   {
                       tmp[idx++]=k;
                   }
                   ans.push_back(tmp);
                   sum-=i; //先-i
                   ++i;
                   ++j;
                   sum+=j; // 后+j
               }
           }
           return ans;
    }
};

0 赞同 0 条回复

Ming 普通 2023年7月13日下午3:47

时间复杂度O(n) O(1) 思路：滑动窗口

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

0 赞同 0 条回复

局外人普通 2023年7月12日下午10:39

思路：滑动窗口思想，因为是连续整数序列，所以可以使用两个端口即可维护一个滑动窗口
时间复杂度O(n) 空间复杂度O(1)

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

        int left=1, right=2, sum=3;

        while(left<right){
            if(sum==target){
                int[] temp = new int[right-left+1];
                for(int i=left; i<=right; i++)
                    temp[i-left] = i;
                res.add(temp);
            }

            if(sum>=target){
                sum -= left;
                left++;
            }else{
                right++;
                sum += right;
            }
        }
        return res.toArray(new int[0][]);
    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年7月12日上午11:13

int[][] 的动态生成，第一次遇到

 public int[][] findContinuousSequence(int target) {
        int n = target/2+1;
        int l = 1, r = 2;
        int cur = 3;
        List<int[]>  res = new LinkedList<>();
        while(r <= n){
            if(cur == target){
                int[] combine = new int[r-l+1];
                for(int i = l; i <= r; i++){
                    combine[i-l] = i;
                }
                res.add(combine);
            }
            if(cur >= target){
                cur -= l++;
            }else{
                r++;
                cur += r;
            }
        }
        return res.toArray(new int[res.size()][]);
    }

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月12日上午12:30

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

    //初始窗口
    int left = 1;
    int right = 1;
    //初始当前sum
    int sum = 1;

    //记录结果
    List<List<Integer>> res = new ArrayList<>();

    while (left <= target / 2){

        if(sum < target){
            right++;
            sum = sum + right;
        } else if (sum > target) {
            sum = sum - left;
            left++;
        }else{
            //记录
            List<Integer> cur = new ArrayList<>();
            for(int i = left;i <= right;i++){
                cur.add(i);
            }
            res.add(cur);
            sum = sum - left;
            left++;

            right++;
            sum = sum + right;
        }
    }

    //将列表转为二维数组
    int [][] dic= new int[res.size()][];

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

        dic[i] = new int[res.get(i).size()];
        for(int j = 0; j < dic[i].length; j++){
            dic[i][j] = res.get(i).get(j);
        } 

    }
    return dic;
}

0 赞同 0 条回复

Jerry 普通 2023年7月11日下午11:15

 

// 滑动窗口
class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1, right = 2, sum = 3;
        List array = new ArrayList<>();
        while (left < right) {
            if (sum == target) { //记录连续整数序列，并向右移动左边界 left++
                int[] answers = new int[right - left + 1];
                for (int index = left; index <= right; index++) {
                    answers[index - left] = index;
                }
                array.add(answers);
            }
            if (sum >= target) { // 向右移动左边界 left++，更新 sum
                sum -= left;
                left++;
            } else { // 向右移动右边界 right++，更新 sum
                right++;
                sum += right;
            }
        }
        return array.toArray(new int[0][]);
    }
}

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

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月11日下午8:58

时间复杂度：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 = sum + j;
            } else if (sum > target){
                sum = sum - i;
                i++;
            } else {
                int[] nums = new int[j - i + 1];
                int index = 0;
                for(int k = i; k <= j; k++){
                    nums[index++] = k;
                }
                list.add(nums);

                sum = sum - i;
                i++;

            }
        }

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

    }
}

0 赞同 0 条回复

yxy 普通 2023年7月11日下午7:57

时间复杂度O(n)

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        if(target<=2) return res;
        int acc = 0, l=1;
        for(int r=1;r<target;r++)
        {
            acc+=r;
            while(acc>target)
            {
                acc-=l;
                l++;
            }
            if(acc==target)
            {
                vector<int> tmp;
                for(int i=l;i<=r;i++)
                    tmp.push_back(i);
                res.push_back(tmp);
            }
        }
        return res;
    }
};

0 赞同 0 条回复

Dsjh 普通 2023年7月11日下午4:32

MY

帅弟

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<int> res;
        vector<vector<int>> ans;
        int l=1,r=1;
        int temp=1;
        while(l <= target/2){
            if(temp < target){
                r++;
                temp += r;
            }
            else if(temp > target){
                temp -= l;
                l++;
            }
            else{
                for(int i=l;i<=r;i++){
                    res.push_back(i);
                }
                ans.push_back(res);
                res.clear();
                temp -= l;
                l++;
                r++;
                temp += r; 
            }
        }
        return ans;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月11日下午3:54

//滑动窗口
//时间复杂度：O(n) 空间复杂度：O(1)
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;
        if(target==1)
        {
            return ans;
        }
        int i,j;
        i=1,j=2;
        int sum=3;
        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)
            {
                j++;
                sum+=j;
            }
            if(sum>target)
            {
                sum-=i;
                i++;
            }
        }
        return ans;
    }
};

0 赞同 0 条回复

张开怀普通 2023年7月11日下午2:53

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

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

共以下 23 个回答

MY

# 回答此问题取消回复

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

共以下 23 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复