剑指offer57-II
依然是双指针的题目,类似于滑动窗口的思想。难点在于边界判断。
本题解提供的代码对边界特判的情况做了详细的注释。
双指针-边界特判(1)
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
if(target < 1)
return {};
int sum = 0, i = 1, j = 1;
vector<vector<int>> res;
int end = target / 2 + 2;
//解释一下这里为什么end == target / 2 + 2;
//在这种写法中,当[i, j)区间内的和等于target时,我们记录该
//序列并使sum += j, j ++ ;即滑动窗口的末尾指针向右移动使区间增大
//也不难发现对于target来说,若
//target为奇数,target/2 + (target / 2 + 1) == target;
//target为偶数,(target/2 - 1) + (target/2 + 1) == target;
//且这两个序列一定是能找到的最后一个和为target的序列。
//已知[i, j)(左闭右开)区间内的sum == target时我们记录该序列,那么
//一定存在j - 1 == target / 2 + 1, 即j == target / 2 + 2时循环必须
//依然可以进行。所以此处的end == target / 2 + 2;
while(j <= end){//这个边界条件需要非常小心,很容易出错。
if(sum < target){
sum += j;
j ++ ;
}
else if(sum == target){
vector<int> temp;
for(int k = i; k < j; k ++ )
temp.push_back(k);
res.push_back(temp);
sum += j;
j ++ ;
}
else{
sum -= i;
i ++ ;
}
}
return res;
}
};
双指针-边界特判(2)
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
if(target < 1)
return {};
int sum = 0, i = 1, j = 1;
vector<vector<int>> res;
int end = target / 2;
//在这种写法中,当[i, j)区间内的和等于target时,我们记录该
//序列并使sum -= i, i ++ ;即滑动窗口的起始指针向右移动使区间减小
//target为奇数,target/2 + (target / 2 + 1) == target;
//target为偶数,(target/2 - 1) + (target/2 + 1) == target;
//且这两个序列一定是能找到的最后一个和为target的序列。
//已知[i, j)(左闭右开)区间内的sum == target时我们记录该序列,那么
//那么在i == max(target/2, target/2 - 1),即 i == target/2时循环
//一定仍可以进行。所以end == target / 2;
while(i <= target){
if(sum < target){
sum += j;
j ++ ;
}
else if(sum == target){
vector<int> temp;
for(int k = i; k < j; k ++ )
temp.push_back(k);
res.push_back(temp);
sum -= i;
i ++ ;
}
else{
sum -= i;
i ++ ;
}
}
return res;
}
};