和为S的连续正数序列
和为S的连续正数序列
http://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe
双指针法,设置两个指针small,big作为一个滑动窗口。当窗口内的和小于sum时big++,判断是否等于sum。如果此时窗口内和大于sum,small++,判断窗口内的和是否等于sum。将寻找到的窗口内数组添加到list中。
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
int small = 1,big = 2;
int mid = (1+sum)/2;
int cursum = small+big;
while (small<mid){
if (cursum == sum){
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < big-small+1; i++) {
temp.add(small+i);
}
list.add(temp);
}
while (cursum>sum&&small<mid){
cursum -= small;
small++;
if (cursum == sum){
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < big-small+1; i++) {
temp.add(small+i);
}
list.add(temp);
}
}
big++;
cursum += big;
}
return list;
}