双指针求和为S的连续正数序列
和为S的连续正数序列
http://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(sum < 3)
return res;
//定义两个指针 左指针为1,右指正为2
int l = 1, r = 2;
//求和
int sumV = l + r;
//在不超出sum的范围
while(r < sum){
//右指针前行,再加入结果
if(sumV < sum){
r++;
sumV += r;
}else if(sumV > sum){ //一旦超出,减去左指针,左指针前移
sumV -= l;
l++;
}else{ //相等,添加进结果集
ArrayList<Integer> list = new ArrayList<>();
for(int i = l; i <= r; i++){
list.add(i);
}
res.add(list);
r++; //右指针右移
sumV += r; //下一轮循环比较
}
}
return res;
}
}
查看9道真题和解析