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

相关推荐

11-08 17:36
诺瓦科技_HR
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务