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

桎梏普通 2023年9月13日下午8:44

//滑动窗口
class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res =  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;
                }
                res.add(ans);
            }
            if (s >= target) {
                s -= i;
                i++;
            }else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[res.size()][]);

    }
}

0 赞同 0 条回复

June 普通 2023年9月9日下午11:02

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> ans = new ArrayList<int[]>();
        int l = 1 , r = 2;
        while(l < r ) 
        {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum < target)
            {
                r++;
            }
            else if (sum > target )
            {
                l++;
            }
            else
            {
                int[] tmp = new int[r-l+1];
                for(int i = l ; i <= r ;i++)
                {
                    tmp[i-l] = i;
                }
                ans.add(tmp);
                r++; // l++ 和 r++都可以
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

0 赞同 0 条回复

hi 普通 2023年9月3日下午6:48

判断数的和与target的关系，小于就加下一个数，等于输出，大于i 往后走

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        for(int i = 1, j = 1, s = 1; i <= target/2; i++)
        {
            while(s < target) s += ++j;
            if(s == target && j > i)
            {
                vector<int> line;
                for(int k = i; k <= j; k++) line.push_back(k);
                res.push_back(line);
            }
            s -= i;
        }
        return res;
    }
};

0 赞同 0 条回复

普通 2023年8月9日下午10:41

c++ 代码
class Solution {
public:
vector<vector> findContinuousSequence(int target)
{
int i=1,j=1,sum=0;
vector<vector> r;
while(i<=target/2)
{
if(sum<target)
{
sum+=j;
j++;
}
else if(sum>target)
{
sum-=i;
i++;
}
else
{
vector cur;
for(int k=i;k<j;k++)
cur.push_back(k);
r.push_back(cur);
sum-=i;
i++;
}

     }return r;
}

};

0 赞同 0 条回复

艺普通 2023年8月5日下午5:10

“`c++
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public:
vector> findContinuousSequence(int target) {
vector> s;
int left = 1;
int right = 1;
int sum = 1;
while(left <= target/2){ if(sum < target){ right++; sum += right; } else if(sum > target){
sum -= left;
left++;
}
else{
vector temp;
for(int i = left; i <= right; i++){ temp.push_back(i); } s.push_back(temp); //保存结果后左边界右移 sum -= left; left++; } } return s; } }; ```

0 赞同 0 条回复

北辰普通 2023年8月4日下午6:46

class Solution {
    public int[][] findContinuousSequence(int target) {
        int n = target/2+1;
        int[] arr = new int[n];
        List<int[]> list = new ArrayList<>();
        for(int i=0;i<n;i++) {
            arr[i]=i+1;
        }
        //System.out.println(Arrays.toString(arr));
        int left=0,right=-1;
        int sum=0;
        while(right<n) {
            if(sum<target) {
                ++right;
                if(right<n) {
                    sum+=arr[right];
                }
                continue;
            }
            if(sum==target) {
                int[] temp = new int[right-left+1];
                int k=0;
                for(int i=left;i<=right;i++) {
                    temp[k++] = arr[i];
                }
                list.add(temp);
            }
            sum-=arr[left];
            left++;
        }
        return list.toArray(new int[list.size()][]);
    }
}

时间复杂度：O（n)

0 赞同 0 条回复

CKX 普通 2023年8月3日下午6:22

func findContinuousSequence(target int) [][]int {
    left, right, sum := 1, 1, 0
    res := [][]int{}
    for left <= target / 2 {
        if sum < target {
            sum += right
            right++
        } else {
            sum -= left
            left++
        }
        if sum == target {
            temp := []int{}
            for i := left; i < right; i++ {
                temp = append(temp, i)
            }
            res = append(res, temp)
            sum -= left
            left++
        }
    }
    return res
}

空间复杂度O(1)

0 赞同 0 条回复

NullPointerException 普通 2023年8月3日下午6:03

class Solution {
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][]);
//从 }
}

0 赞同 0 条回复

#00456B 普通 2023年8月3日下午3:08

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        //滑动窗口的方法
        vector<vector<int>> ans;
        //定义左右边界
        int left = 1;
        int right = 1;
        int sum = 1;
        while(left <= target/2){//至少两个数，所以左边界的边界条件为target/2
            if(sum < target){
                right++;
                sum += right;
            }
            else if(sum > target){
                sum -= left;
                left++;
            }
            else{
                vector<int> temp;
                for(int i = left; i <= right; i++){
                    temp.push_back(i);
                }
                ans.push_back(temp);
                //保存结果后左边界右移
                sum -= left;
                left++;
            }
        }
        return ans;
    }
};

0 赞同 0 条回复

Mby 普通 2023年8月2日下午8:46

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

Marshan 普通 2023年8月2日下午4:31

不难,但是要搞清楚细节(是[left,right]还是[left,right))

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

0 赞同 0 条回复

AD钙奶普通 2023年7月31日下午3:03

滑动窗口

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) {
                int[] arr = new int[j - i + 1];
                for(int k = i, t = 0; k <= j; k ++) {
                    arr[t ++] = k;
                }
                sum -= i;
                ++ i; 
                ++ j;
                sum += j;
                list.add(arr);
            } else if(sum > target) {
                sum -= i;
                i ++;
            } else {
                j ++;
                sum += j;
            }
        }
        int[][] result = list.toArray(new int[list.size()][]);
        return result;
    }
}

0 赞同 0 条回复

Luminous 普通 2023年7月31日上午11:25

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

以上是代码

0 赞同 0 条回复

mpweixin用户普通 2023年7月31日上午11:16

// 双指针
class Solution {
    public int[][] findContinuousSequence(int target) {

        List<int[]> vec = new ArrayList<int[]>();
        for (int l = 1, r = 2; l < r;) {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] res = new int[r - l + 1];
                for (int i = l; i <= r; ++i) {
                    res[i - l] = i;
                }
                vec.add(res);
                l++;
            } else if (sum < target) {
                r++;
            } else {
                l++;
            }
        }
        return vec.toArray(new int[vec.size()][]);

    }

    }

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月30日下午9:48

7.30
Day21：下面是代码

class Solution {
    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;即第一位就是ans[0]
                    ans[k - i] = k;   
                }
                res.add(ans);
            }
            if(s >= target){
                s -= i;
                i++;
            }else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }
}

0 赞同 0 条回复

人生何处不青山普通 2023年7月30日下午8:41

总和比target小就右边界++，比target大就左边界++

function findContinuousSequence(target: number): number[][] {
    if(target <= 1) return [];
    let l = 1,r = 1;
    let res: number[][] = [];
    while( r <= Math.floor(target / 2) + 1) {
        let tmp = [];
        while(sum(l,r) < target) r++;
        while(sum(l,r) > target) l++;
        if(sum(l,r) === target) {
            for(let i = l;i <= r;i++) {
                i !== 0 && (tmp.push(i));
            }
            tmp.length && (res.push(tmp.slice()));
            r++;
        }
    }
    return res;
};

function sum(l: number, r: number): number {
    return (l + r) * (r - l + 1) / 2;
}

0 赞同 0 条回复

阿尚普通 2023年7月30日下午7:27

滑动窗口
class Solution {
    public int[][] findContinuousSequence(int target) {
        ArrayList<int[]> resList = new ArrayList<>();
        int left = 1;
        int sum = 0;
        for(int i = 1; i <= target / 2 + 1; i++){
            sum += i;
//滑动窗口题目关键在于左边界的移动条件
            while(sum >= target){
                if(sum == target){
                    int[] arr = new int[i - left + 1];
                    for(int j = left; j <= i; j++){
                        arr[j - left] = j;
                    }
                    resList.add(arr);
                }
                sum -= left;
                left++;
            }
        }

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

0 赞同 0 条回复

【数学知识】剑指 Offer 57 – II. 和为s的连续正数序列

共以下 17 个回答

# 回答此问题取消回复

【数学知识】剑指 Offer 57 – II. 和为s的连续正数序列

共以下 17 个回答

# 回答此问题 取消回复

# 回答此问题取消回复