其他算法/数组前缀和

学习笔记

问题描述

sum(arr,L,R), 查询数组L…R的累加和， 比如数组 [1,2,3,4,5], sum(1,3) 就是下标是2,3,4的数组区间和累加和 即 2+3+4 = 9

  1. 暴力循环解法
    当需求需要查询这种范围的结果特别频繁时,考虑使用如下两种方法。
  2. 二维数组空间换时间解法
    二维数组计算出所有情况的累加和，但是需要空间复杂度O(n^2/2),时间复杂度O(1).
  3. 前缀和解法
    一维辅助数组计算数组的前缀和，空间复杂度O(n),时间复杂度O(1) ,
    k的前缀和概念就是arr[0,k]的累加和， sum(arr,L…R) = help[R] - help[L-1] , 如果L=0，前缀和即是help[R].

代码实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class Prefix_num_sum {
    public static void main(String[] args) {
        //测试 二维数组空间换时间
        int[] arr1 = new int[]{1,3,2,2,3,4,3,2,5};
        initSumOfRangeL_R(arr1);
        System.out.println(getSumOfRangeL_R(0,2));

        //测试 前缀和
        int[] arr2 = new int[]{1,3,2,2,3,4,3,2,5};
        initPreSum(arr2);
        System.out.println(getPreSum(arr2,0,2));

    }
    /**
     * 暴力解法
     * @param arr
     * @param L
     * @param R
     */
    public static int  simpleSumOfRangeL_R(int[] arr, int L , int R){
        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            if (i >= L  && i <=R) {
                result += arr[i];
            }
        }
        return result;
    }

    /**
     * 二维数组空间换时间解法
     */
    private static int[][] help ;
    // 二维数组计算L...R区间的累加和实现
    public static void initSumOfRangeL_R(int[] arr) {
        int N = arr.length;
        help = new int[N][N];
        //初始化二维数组 horizontal 水平  vertical 垂直
        for (int hor = 0; hor < N; hor++) {
            for (int ver = 0; ver < N; ver++) {
                if (hor == ver) {
                    help[hor][ver] = arr[hor];
                } else if(hor > ver & hor > 0) {
                    help[hor][ver] = help[hor - 1][ver] + arr[hor];
                }
            }
        }
    }
    public static int getSumOfRangeL_R(int L, int R) {
        if (L > R) return 0;
        // 取值不要弄反横纵坐标
        return help[R][L];
    }

    /**
     * 一维辅助数组计算数组的前缀和
     */
    private static int[] preSumHelp;
    public static void initPreSum(int[] arr) {
        int N = arr.length - 1;
        preSumHelp = new int[N];
        preSumHelp[0] = arr[0];
        for (int i = 1; i < N; i++) {
            preSumHelp[i] = preSumHelp[i-1] + arr[i] ;
        }
    }
    public static int getPreSum(int[] arr, int L ,int R) {
        if (L > R) return 0;
        //如果从0开始，直接取R的前缀和，L大于0，则需要相减
        return L == 0 ? preSumHelp[R] : preSumHelp[R] - preSumHelp[L-1];
    }
}