题解 | #和为S的连续正数序列#
和为S的连续正数序列
https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
#include <vector> class Solution { public: vector<vector<int> > FindContinuousSequence(int sum) { // write code here if (sum == 0) return vector<vector<int>>{};// 剔除空情形 int l = 1, r = 1;// 题意取值范围1~100,故一开始左右指向都是1 int tmp_sum = 0; vector<int> tmp_v; vector<vector<int>> res; while(l <= r && r <= sum/2+1)// 保证一直找,并且最大遍历访问也是就sum/2 + 1 { tmp_sum = (l+r)*(r-l+1)/2;//等差数列求和公式理解 // std::cout << tmp_sum <<" " << i <<" " <<l << " " << r<< std::endl; if(sum == tmp_sum) { for(int j = l; j <= r; ++j) { tmp_v.push_back(j); } if(tmp_v.size() > 1) res.push_back(tmp_v);// 题意至少两个数,故剔除较小值时的异常情况 tmp_v.clear(); l++;// 但满足时,需要更新左指向,否则会一直死循环 } else if(tmp_sum < sum) // 和比目标值小,则右指针右移动 { r++; } else // 和比目标值大,则缩减左值向右移动 { l++; } } // std::cout << res.size() << std::endl; return res; } };
挤挤刷刷! 文章被收录于专栏
记录coding过程