剑指Offer 和为S的连续正数序列(JZ41)

题目简述:

• 给你一个数字sum，求出所有满足连续的正数序列的和为sum的序列（序列中至少包含两个数）

算法一：前缀和+枚举

时间复杂度：O(n*n)
算法思路：

1. 前缀和就是可以在O(1)的时间复杂度里查找出[l,r]的区间和,方法是s[r]-s[l-1];

• 原理:
  s[r] = a[1] + a[2] + a[3] + ... + a[l-1] + a[l] + ... + a[r] ;
  s[l-1] = a[1] + a[2] + a[3] + ... + a[l-1] ;
  做差：s[r] - s[l-1] = a[l] + a[l+1] + ... + a[r] ;
  注意： 数组下标从将s[0]初始化为0，下标从1开始，防止数组越界。

2. 枚举从1~sum，以 i 作为起点，枚举i后面的下标 j ，判断从i到j的元素和是否等于sum，方法就是判断 s[j]-s[i-1]==sum ，若等于则 i 到 j 即为其中的一个答案；

代码：

class Solution {
public:
 vector<vector<int> > FindContinuousSequence(int sum) {
     vector<vector<int> > res;
     vector<int> s;
     s.push_back(0);
     for(int i=1;i<sum;i++){ //预处理前缀和
         int t=i+s[i-1];
         s.push_back(t);
     }
     for(int i=1;i<sum;i++){
        int r;
         for(int j=i+1;j<sum;j++){
             if(s[j]-s[i-1]>=sum){
                 r=j;
                 break;
             }
         }
         if(s[r]-s[i-1]==sum){//若符合条件则将结果存入ans中
             vector<int> ans;
             int t=i;
             while(t<=r) ans.push_back(t++);
             res.push_back(ans);
         }
     }
     return res;
 }
};

算法二:前缀和+二分查找

时间复杂度：O(nlogn)
算法思路：

1. 在算法一的基础上加以优化，使查找的时间复杂度从O(n)下降为O(logn)。
2. 由于都是正数 ，所以整个前缀具有单调性 ，在遍历当前元素i的的时候，我们直接二分满足s[mid]-s[i-1]>=sum的第一个元素的位置 r ，然后判断查找出来的结果是否满足s[r]-s[i-1]==sum，若等于区间[i,r]的元素即为其中的一个答案。

代码：

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > res;
        vector<int> s;
        s.push_back(0);
        for(int i=1;i<sum;i++){//预处理前缀和
            int t=i+s[i-1];
            s.push_back(t);
        }
        for(int i=1;i<sum;i++){
           int l=0,r=s.size()-1;//查找范围从 0,s.size)  
            while(l<r){  
            int mid=l+r>>1;  
            if(s[mid]-s[i-1]>=sum) r=mid;  
            else l=mid+1;  
            }
            if(s[r]-s[i-1]==sum){//若符合条件则将结果存入ans中
                vector<int> ans;
                int t=i;
                while(t<=r) ans.push_back(t++);
                res.push_back(ans);
            }
        }
        return res;
    }
};