JZ41-和为S的连续正数序列
和为S的连续正数序列
https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
int start = 1, end = 2;
int curSum = 3;
while (end < sum) {
if (curSum > sum) {
curSum -= start; //必须先减去不需要的
start++; //窗口向左缩小
} else if (curSum < sum) {
end++; //窗口向右增加，左边界不变
curSum += end; //加上新的值
} else {
ArrayList<Integer> list = new ArrayList<>();
for (int i = start; i <= end; i++) {
list.add(i);
}
ret.add(list);
curSum -= start; //窗口整体右移，两边都+1。
start++;
end++;
curSum += end;
}
}
return ret;
}
}
class Solution2 {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
for (int i = 1; i < (sum >> 1) + 1; i++) { //分别从 1 2 3开头，看是否满足条件
int temp = 0;
int j = i;
while (temp < sum) {
temp += j;
j++;
}
if (temp == sum) {//如果找到了那么就要把数据添加到结果数据中。
ArrayList<Integer> newArray = new ArrayList<>();
for (int k = i; k < j; k++)
newArray.add(k);
result.add(newArray);
}
}
return result;
}
} 
