描述:給定一個和S,找出和為S的連續(xù)序列,如9:[2,3,4], [4,5]
分析:網(wǎng)上許多方法中,印象最深刻的是雙指針法。兩個指針限定區(qū)間的范圍和大小。
vector<vector<int>> CumSum(int S)
{
vector<vector<int>> res;
vector<int>temp;
int low = 1, high = 2;
while(low<high)
{
// 計算當(dāng)前區(qū)間的和
int cur_sum = (low+high)*(high-low+1)/2;
if(cur_sum == S)
{
for(int I = low; I<= high; I++)
temp.push_back(i);
res.push_back(temp);
temp.clear();
low++;
}
else
if(cur_sum < S)
// 區(qū)間和比S小,右邊界右移,擴(kuò)
high++;
else
// 區(qū)間和比S大,左邊界右移,縮
low++;
}
return res;
}