剑指offer- II. 和为s的连续正数序列

这是一道数学题,自己连“暴力法”都没想出来!

看了题解

法一:枚举 + 暴力法

枚举每个正整数为起点,判断以它为起点的序列和 sum 是否等于 target 即可,由于题目要求序列长度至少大于 2 ,所以枚举的上界为 (target-1)/2

法二:窗口滑动+双指针法

我们用两个指针 l (left) 和 r (right)  表示当前枚举到的以 l 为起点到  r 的区间,sum 表示 [l,r] 的区间和,求得 sum= (l+r)*(r-l+1) /2

起始 l=1,r=2

一共有三种情况:

如果 sum<target 则说明指针 r 还可以向右拓展使得 sum 增大,此时指针 r 向右移动,即 r+=1

如果 sum>target 则说明以 l 为起点不存在一个 r 使得 sum=target,此时要枚举下一个起点,指针 l 向右移动,即 l+=1

如果sum==target 则说明我们找到了以 l 为起点得合法解 [l,r] 我们需要将 [l,r] 的序列放进答案数组,且我们知道以 l 为起点的合法解最多只有一个,所以需要枚举下一个起点,指针 l 向右移动,即 l+=1

终止条件即为 l>=r 的时候,这种情况的发生指针 r 移动到了 ⌊target / 2⌋+1 的位置,导致 l<r 的时候区间和始终大于 target.


题目


code

官方题解

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容