剑指 Offer 57 - II. 和为s的连续正数序列
难度:简单
输入一个正整数 target
,输出所有和为 target
的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
示例 1:
输入:target = 9
输出:[[2,3,4],[4,5]]
示例 2:
输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]
限制:
题目分析:
这道题应该是中等难度,主要思想是双指针和滑窗,仔细观察这个题目,说是输入一个target,输出连续正数序列。那么显然是要连续的,我们想到双指针和滑窗,通过双指针改变窗口大小即可,不需要超过target的一半,因为后一半都不满足条件的(滑窗相加都会超过target)。这里因为是连续的序列,所以我们使用数学公式(left+right)*(right-left+1)/2,进行求解和。那我们分析一下情况,进行讨论:
(1)sum小于target的情况,那么显然右边指针向右移动,right++
(2)sum大于target的情况,显然左指针向右移动,left++
(3)sum等于target的情况下,显然枚举一下,将连续数组放入结果中,并且left++
参考代码:
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
int left = 1;
int right = 2;
vector<int> temp;
vector<vector<int>> res;
while(left <= right && right <= (target+1)/2)
{
int sum = (left+right)*(right-left+1)/2;
if(sum < target)
{
right++;
}else if(sum > target)
{
left++;
}else{
temp.clear();
for(int i = left; i <= right; i++)
{
temp.push_back(i);
}
res.push_back(temp);
left++;
}
}
return res;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)