# 1. 一维前缀和

先看两道 leetcode 题：

第一道是实现前缀和，第二道是前缀和的应用求区域和。

下面代码展示：

# 1 - 求前缀和

两种方式：

求区间 [L,R] 元素和时，取出 preNum[R] 和 preNum[L-1] ，作差即可。

一个二维矩阵，缺点是前面生成二维矩阵的时候要花时间和空间。时间复杂度 n*n/2 ，空间 n * n

但是当你需要做超多次求区间和操作的时间，你可以直接拿出来不用运算。

代码：可以直接粘到 idea 中执行，由 mian 方法

	/**
	* 这里提供的方案是创建一个跟数组一样大小的数组，里面 0-i 的前缀和
	* 要求 2~7 之间的和的时候就是就 arr [7]-arr [1]
	*/
	public static int[] getPreNum(int[] arr){
	if(arr==null \|\| arr.length<2){
	return arr;
	}
	int N=arr.length;
	int[] preNum=new int[N];
	preNum[0]=arr[0];
	for (int i = 1; i < N-1; i++) {
	preNum[i]=preNum[i-1]+arr[i];
	}
	return preNum;
	}

	/**
	* 求数组 arr 的第 L 位到第 R 位的之间数字的和 (区域和)
	*/
	public static int preNum(int[] arr,int L,int R){
	int[] preNum=getPreNum(arr);
	int ans = L==0?preNum[R]:preNum[R]-preNum[L-1];
	return ans;
	}

	public static void main(String[] args) {
	int[] arr={1,5,0,-10,5,18,10};
	System.out.println(preNum(arr,0,0));
	System.out.println(preNum(arr,0,1));
	System.out.println(preNum(arr,0,2));
	System.out.println(preNum(arr,1,3));
	}

当然还有二维的，一样的道理：就是下面这样的原理。

sorry，我懒了。代码不复杂我不写了，感兴趣的自己实现一下。

算法