双指针求和为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;
    }
}
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务