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

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-27 18:00:30
    编辑于：2022-02-27 19:42:26
    浏览量：860

概述

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

暴力法

O(n^2) 的时间复杂度。

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> ans;
        for (int i = 1; i < target; i ++) {
            vector<int> t;
            int sum = 0;
            for (int j = i; j < target; j ++) {
                sum += j;
                t.push_back(j);
                if (sum == target) {
                    ans.push_back(t);
                    break;
                } else if (sum > target) {
                    break;
                }
            }
        }
        return ans;
    }
};

基于前缀和和哈希表的解法

首先构造前缀和，之后对于每一个起始点，我们可以推算出目标结束点的前缀和，O(1) 查下哈希表就好了。

另外实现的时候要注意前缀和中数字可能溢出。

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<long> sums(target + 1);
        unordered_map<int, int> sum2idx;
        for (int i = 1; i <= target; i ++) {
            sums[i] = sums[i-1] + i;
            sum2idx[sums[i]] = i;
        }
        vector<vector<int>> ans;
        for (int i = 0; i <= target; i ++) {
            int query = target + sums[i];
            if (sum2idx.count(query) != 0) {
                int j = sum2idx[query];
                vector<int> tmp;
                for (int k = i + 1; k <= j; k ++) tmp.push_back(k);
                if (tmp.size() > 1) ans.push_back(tmp);
            }
        }
        return ans;
    }
};

前后指针

虽然时间复杂度和空间复杂度是一样的，但是该解法的执行时间和内存消耗该解法相较于前两者小了一个数量级。

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

Links: sword-offer-57-2