[leetcode刷题]|[leetcode刷题] 和为s的连续正数序列
题目传送门
1.滑动窗口 因为结果是连续序列，所以可用头哨兵尾哨兵来唯一确定一个序列。序列的和也可以计算出。因此有n*n个序列需要去判断。
但是当知道了某序列的值已经比target要大，则相同起点更长的序列不需要判断，所以可以剪枝掉一部分，因此有滑动窗口一说。
【[leetcode刷题]|[leetcode刷题] 和为s的连续正数序列】具体流程：
序列初始为[1]其值为1（如果是0会错）。
小于target时头走一步（可根据增量来计算出新序列的值）
大于target时尾走一步
相等时记录（两者任意走一步即可）
class Solution {
public:
vector> findContinuousSequence(int target) {//record
vector> result;
int sum = 1;
//boundary
int l = 1;
int r = 1;
int sidx = 1;
int eidx = target/ 2 + 1;
//main
while (l <= r && r <= eidx){
if (sum == target){
//cout<<1< tmp_vec;
for(int i = l;
i <= r;
i++)
tmp_vec.push_back(i);
result.push_back(tmp_vec);
sum -= l++;
sum += ++r;
} else if (sum < target){
//cout<<2< target){
//cout<<3< 2.计算 因为所求为连续序列，可以设序列中位数为x，数量为n，则target=n*x
奇数序列时，中位数就是序列中间的数
偶数序列时，中位数就是序列中间两个数的平均值，可以认定是两者中较小的数字+0.5
（tips:当target翻倍时，中位数是整数）
所以在某个确定的长度n下，可以通过计算算出是否有序列存在。
而n的边界的话，因为初始化序列为[1]，则n应该从1开始增加，最大值为可能出现的最长的序列。
最长的序列应该是从1开始到x，其值为(x+1)*x/2
class Solution {
public:
vector> findContinuousSequence(int target) {//record
vector> result;
int n = 1;
//boundary
int limit = sqrt(target*2) + 1;
//main
while ( ++n <= limit ){
if( (n%2==1 && target%n==0) ||
(n%2==0 && target%n!=0 && target*2%n==0) ){ //奇数列 中位数是整数偶数列 中位数是0.5小数int mid = target / n;
vector tmp_vec;
if( n%2 == 1 ){ //奇数序列
for (int i = mid - (n-1)/2;
i <= mid + (n-1)/2 ;
i++)
tmp_vec.push_back(i);
}else {
for (int i = mid - (n-1)/2;
i <= mid + (n-1)/2 + 1 ;
i++)
tmp_vec.push_back(i);
}
if(tmp_vec[0] != 0)
result.push_back(tmp_vec);
}
}
reverse(result.begin(), result.end());
return result;
}
};
推荐阅读
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- leetcode|leetcode 92. 反转链表 II
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- LeetCode（03）Longest|LeetCode（03）Longest Substring Without Repeating Characters
- Leetcode|Leetcode No.198打家劫舍
- [leetcode数组系列]1两数之和
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- LeetCode|LeetCode 876. 链表的中间结点