题目简述:
给定一个数字sum,求出所有满足连续的正数序列的和为sum的序列(序列中至少包含两个数)。
算法一:前缀和+枚举
时间复杂度:O(n2)
算法思路:
1. 前缀和 ( s[i]=a[1]+a[2]+...+a[i] ): 可以在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; } };