营销策划方案网站,店铺网站域名怎么做,jsp网站开发典型模块与实例精讲,网站专业建设公司输入一个正整数 target #xff0c;输出所有和为 target 的连续正整数序列#xff08;至少含有两个数#xff09;。
序列内的数字由小到大排列#xff0c;不同序列按照首个数字从小到大排列。 示例 1#xff1a;
输入#xff1a;target 9 输出#xff1a;[[2,3,4],[4…输入一个正整数 target 输出所有和为 target 的连续正整数序列至少含有两个数。
序列内的数字由小到大排列不同序列按照首个数字从小到大排列。 示例 1
输入target 9 输出[[2,3,4],[4,5]] 示例 2
输入target 15 输出[[1,2,3,4,5],[4,5,6],[7,8]]
限制
1 target 10^5
暴力解通过
注意子序列长度大于等于二所以我们循环以二分之一个目标作为结束标志当然也要注意一下要不要1以及循环结束条件是小于等于还是等于的问题。 AC代码
class Solution {
public:vectorvectorint findContinuousSequence(int target) {int start 1;vectorvectorintresult;vectorintsmallresult;int half_target (target*0.5) 1;while (start half_target){int sum 0;int flag 0;smallresult.clear();for (int i start;i half_target;i){flag 1;sum i;smallresult.push_back(i);if (sum target){break;}else if (sum target){result.push_back(smallresult);break;}}if (flag 1) start;}return result;}
};优化暴力解
优化之后的代码仍然是暴力法不过将push_back换成了emplace_back然后将插入和清除操作放入了sum target的逻辑块中减少了插入以及删除元素带来的时间损失。
class Solution {
public:vectorvectorint findContinuousSequence(int target) {int start 1;vectorvectorintresult;vectorintsmallresult;int half_target (target*0.5) 1;while (start half_target){int sum 0;int flag 0;for (int i start;i half_target;i){flag 1;sum i;if (sum target){break;}else if (sum target){smallresult.clear();for(int jstart;ji;j) smallresult.emplace_back(j);result.emplace_back(smallresult);break;}}if (flag 1) start;}return result;}
};再次优化思路
一开始我列下了两个优化思路 1、若只有一组结果或者没有结果能不能找到一种方法直接返回结果 2、如果已经完成一组结果下一组的推断能不能用到上一组的信息。 接下来就是一大堆乱改步长的操作也就是说之前每完成一次子序列和没有完成子序列下一次的起始点都是原起始点1此时我们不这样做而是在完成一次子序列后修改下一次的起始点。 修改思路 此处的i是指完成一次子序列时的子序列的右边界 1、new_start(istart)0.51; 经过验证是错误的 2、new_start i0.51 (经过验证是错误的 3、new_startstart2; 这个倒是可以。。。不过优化不是很多
双指针滑动窗口
我们用两个指针 L 和 R 表示当前枚举到的以 L 为起点到 R 的区间sum 表示[L,R]的区间和由求和公式可知; 也就是说如果确定了一对L、R就可以直接得到sum值而不需要累加计算了省时序 如果sumtarget 则说明指针R还可以向右拓展使得sum 增大此时指针R向右移动即 r1 如果sumtarget 则说明以L为起点不存在一个R使得 sumtarget此时要枚举下一个起点指针L向右移动即l1 如果sumtarget 则说明我们找到了以L为起点得合法解 [l,r]我们需要将 [l,r][l,r] 的序列放进答案数组且我们知道以L为起点的合法解最多只有一个所以需要枚举下一个起点指针L向右移动即 l1 (题外话官方解的第三种方法讲解有问题。。。) 而且感觉这个方法也没有用到区间信息只是高级在使用了公式。
class Solution {
public:vectorvectorint findContinuousSequence(int target) {vectorvectorintvec;vectorint res;for (int l 1, r 2; l r;){int sum (l r) * (r - l 1) / 2;if (sum target){res.clear();for (int i l; i r; i) res.emplace_back(i);vec.emplace_back(res);l;}else if (sum target) r;else l;}return vec;}
};另外还发现了一个C语法的问题 c11 之emplace_back 与 push_back的区别 总结就是能用emplace_back就用emplace_back。
