剑指Offer57 II. 和为s的连续正数序列

发表于 | 分类于 |
字数统计: 456 | 阅读时长 ≈ 2

链接: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

题意

输入一个正整数 target ，输出所有和为 target 的连续正整数序列

解法

乍看之下是道简答题
但还是花了一点时间写了一下
主要考虑两种做法
一种是我自己写的做法，每次枚举左端点，然后二分右端点算出答案是否符合要求
时间复杂度为O(nlogn)

一个比较好的做法是双指针
我们用两个指针 l 和 r 表示当前枚举到的以 l 为起点到 r 的区间，每次计算sum
如果sum > target 则说明以l为起点不存在和为sum的值，l自增1
如果sum < target 则说明这时候r还可以向右扩展让sum增大，r自增1
如果sum = target 此时的l和r为一组解，存入最后的结果
时间复杂度为O(n)

代码

二分答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    bool check(int l, int r, int target) {
        long long ans = 1LL * (l + r) * (r - l + 1) / 2;
        return ans >= target;
    }
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;
        for (int i = 1; i <= target / 2; i++) {
            int l = i, r = target;
            while(r - l > 1) {
                int mid = l + (r - l) / 2;
                if (check(i, mid, target)) {
                    r = mid;
                }
                else {
                    l = mid;
                }
            }
            if (1LL * (i + r) * (r - i + 1) / 2 == target) {
                vector<int> temp;
                for (int j = i; j <= r; j++) {
                    temp.push_back(j);
                }
                ans.push_back(temp);
            }
        }
        return ans;
    }
};

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;
        for (int l = 1, r = 2; l < r; ) {
            int sum = 1LL * (l + r) * (r - l + 1) / 2;
            if (sum > target) {
                l++;
            }
            else if (sum < target){
                r++;
            }
            else {
                vector<int> temp;
                for (int i = l; i <= r; i++) {
                    temp.push_back(i);
                }
                ans.push_back(temp);
                l++;
            }
        }
        return ans;
    }
};