剑指OFFER-和为S的连续正数序列

QuestionSolution暴力循环双指针

Question

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck! 输出描述： 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

关键词：连续求和 双指针

Solution

暴力循环

从小到大每一个可能的数字开头，往后加到目标，太大了就结束当前数字。可能的数字大于等于1，小于等于目标的一半（因为至少要两个数字相加）。 时间复杂度：O(N^2) 空间复杂度：O(1)

Python class Solution: def FindContinuousSequence(self, tsum): ans = [] for s in range(1, tsum//2+1): temp = [s] end = s+1 temp_sum = s while temp_sum < tsum: temp_sum += end if temp_sum > tsum: temp = [] break temp.append(end) if temp_sum == tsum: break end += 1 if len(temp)>1: ans.append(temp) return ans C++ class Solution { public: vector<vector<int> > FindContinuousSequence(int sum) { vector<vector<int> > ans; vector<int> temp; for(int i=1; i<=sum/2; i++){ int start = i; int end = i+1; int temp_sum = i; temp = {i}; while (temp_sum < sum){ temp_sum += end; if(temp_sum > sum){ temp.clear(); break; } temp.push_back(end); if(temp_sum == sum) break; end++; } if(temp.size()>1) ans.push_back(temp); } return ans; } };

双指针

暴力循环的缺点是重复计算了区间，比如第一次我从1加到10，溢出了，接下来我尝试从2往上加，可能加到9，那么2~9这个区间被重复算了两次，之后可能还有更多次。为了避免重复，如果从1加到10：不够，继续加11；溢出，减掉一个最小值，也就是最左边的1，试试看够不够。 总而言之就是用两个指针来指向区间两端（这样还不用循环求和，用公式就好了），区间之和等于目标，答案加上这个区间，左边往右移动（成功，下一个可能）；小于目标，右边往右移动一个（还没到，继续走）；大于目标，左边往右移动一个（这个区间不可能啦，下一个）。

时间复杂度：O(N) 空间复杂度：O(1)

Python class Solution: def FindContinuousSequence(self, tsum): p1, p2 = 1, 2 ans = [] while p1<p2: temp = (p1+p2)*(p2-p1+1)/2 if temp == tsum: path = [i for i in range(p1, p2+1)] ans.append(path) p1 += 1 elif temp<tsum: p2 += 1 else: p1 += 1 return ans C++ class Solution { public: vector<vector<int> > FindContinuousSequence(int sum) { vector<vector<int> > ans; int p1=1, p2=2; while(p1 < p2){ int temp_sum = (p1+p2)*(p2-p1+1)/2; if (temp_sum == sum){ vector<int> temp; for(int i = p1; i<=p2; i++) temp.push_back(i); ans.push_back(temp); p1++; } else if(temp_sum < sum) p2++; else p1++; } return ans; } };