和为S的连续正数序列

云计算 waitig 471℃ 百度已收录 0评论

题目描述:

现在要求有多少种连续的正数序列的和为100(至少包括两个数)。其中一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? 

思路:

由于题目要求至少包含两个数,那么所有可能的序列的最大值均不会超过(sum + 1) >> 1;
1, 2, start-1, start, start+1, start+2, ..., end-1 , end.
于是,从 end= (sum + 1)>> 1, start = end - 1 开始求和。
while( start > 0){
    tmp += start;
    if(tmp == sum)
        将 start, ..., end记录下来;
        tmp -= end;
        end--;
        start--;
    else if(tmp < sum)
        start--;
    else //tmp > sum
        tmp -= end;
        end--;
        start--;
    //每比较一次,需要更新start,end,tmp的值
}

时间复杂度为O(start) = O(sum)

代码实现如下:

import java.util.ArrayList;

public class SequenceSum {

    public static void main(String[] args) {
        int target = 9;
        for (ArrayList<Integer> list : findSequence(target)) {
            for (int x : list)
                System.out.print(x + " ");
            System.out.println("");
        }
    }

    private static ArrayList<ArrayList<Integer>> findSequence(int sum) {
        if (sum <= 2)
            return new ArrayList<>();
        int end = (sum + 1) >> 1, start = end - 1, tmp = end;
        ArrayList<ArrayList<Integer>> aal = new ArrayList<>();
        while (start > 0) {
            tmp += start;
            if (tmp == sum) {
                ArrayList<Integer> al = new ArrayList<>();
                for (int i = start; i <= end; i++) {
                    al.add(i);
                }
                aal.add(al);
                tmp -= end;
                end--;
            } else if (tmp > sum) {
                tmp -= end;
                end--;
            }
            start--;

    }
}

输出如下:

4 5 
2 3 4 

也可以根据序列start从小到大输出序列
aal.add(0,al);
但是由于ArrayList是基于数组实现的,每次调用add(0,al)必然导致0以后的所有值需要后移一位,效率低下。可以将ArrayList换成LinkedList,这样效率会高一些,特别是链表较长时,效率会更高。


本文由【waitig】发表在等英博客
本文固定链接:和为S的连续正数序列
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)