求和数组连续序列

1、问题简述

1.随机生成一个数字数组
2.计算每个连续序列的和
 例： 1 2 3 4 5
 	1+2, 1+2+3, ...
 	2+3, 2+3+4, ...
3.给定一个值，匹配序列的和，相同的则输出（序列）；没有符合的就输出 -1
 例：给定值为5，输出序列：
 2 3
 5
1
2
3
4
5
6
7
8
9

2、程序

2.1 计算数组的所有序列和

/**
 * 数组按顺序求和
 * @param params    需要求和的数组
 * @param 
 * @return	数组，下标i表示参数数组前i位的和
 */
private static <T extends Integer > Integer[] sumArray(T[] params) {
    int size = params.length;
    Integer[] result = new Integer[size];
    int temp = 0;
    for (int i = 0; i < size; i++) {
        temp += Integer.valueOf(params[i]);
        result[i] = temp;
    }
    return result;
}
/*
[1, 3, 6, 10, 15]
[2, 5, 9, 14]
[3, 7, 12]
[4, 9]
[5]
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.2 获取符合的对应下标

for (int i = 0; i < arr.length; i++) {
    // 拆分数组，分别求序列和 [1,2,3,4,5],[2,3,4,5]...
    Integer[] integers = sumArray(Arrays.copyOfRange(arr, i, arr.length));
    int j = Arrays.binarySearch(integers,VALUE);
    if(j >= 0) {
        // 表示匹配成功,i 为求和的起点，j 为终点
        // 例: i=1,求和数组为 [2,3,4,5], 和为[2, 5, 9, 14],匹配得出j为1；则对应的数组序列是 [i,i+j+1]
    }
}
1
2
3
4
5
6
7
8
9

3、完整

public class MaximumSequence {
    // 数组长度
    private final static int MAX_SIZE = 5;
    // 复杂度
    private static long complexity = 0;
	// 匹配的值
    private final static int VALUE = 5;

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,2,3,4,5};

        System.out.println(Arrays.toString(arr));
        for (int i = 0; i < arr.length; i++) {
            ++complexity;
            Integer[] integers = sumArray(Arrays.copyOfRange(arr, i, arr.length));
            int j = Arrays.binarySearch(integers,VALUE);
            System.out.print("序列 " + (i + 1) + "：");
            if(j >= 0) {
                System.out.println(Arrays.toString(Arrays.copyOfRange(arr,i,i + j + 1)));
            }else {
                System.out.println("-1");
            }
        }
        System.out.println("执行次数：" + complexity);
    }

    /**
     * 数组按顺序求和
     */
    private static <T extends Integer > Integer[] sumArray(T[] params) {
        int size = params.length;
        Integer[] result = new Integer[size];
        int temp = 0;
        for (int i = 0; i < size; i++) {
            ++complexity;
            temp += Integer.valueOf(params[i]);
            result[i] = temp;
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

4、执行结果

可见复杂度为 !o

[1, 2, 3, 4, 5]
序列 1：-1
序列 2：[2, 3]
序列 3：-1
序列 4：-1
序列 5：[5]
执行次数：20
1
2
3
4
5
6
7