Cinte's Leetcode Record
0%

剑指 Offer 57 - II. 和为s的连续正数序列

Posted on Edited on In Disqus:
Symbols count in article: 912 Reading time ≈ 1 mins.

剑指 Offer 57 - II. 和为s的连续正数序列

暴力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ret;
        for(int i = 1; i <= target >> 1; ++i)
        {
            int sum = i;
            vector<int> tmp;
            tmp.push_back(i);
            for(int j = i + 1; j < target; ++j)
            {
                tmp.push_back(j);
                sum += j;
                if(sum > target)
                    break;
                else if(sum == target)
                    ret.push_back(tmp);
            }
        }
        return ret;
    }
};

T(n) : O(n^2)

sliding window
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
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int begin = 1, end = 1, sum = 0;
        vector<vector<int>> ret;
        while(begin < (target >> 1))
        {
            sum += end;
            while(sum >= target)
            {
                if(sum == target)
                {
                    vector<int> tmp;
                    for(int i = begin; i <= end; ++i)
                        tmp.push_back(i);
                    ret.push_back(tmp);
                }
                sum -= begin;
                ++begin;
            }
            ++end;
        }
        return ret;
    }
};

T(n) : O(n)