计算一个数组中L位置到R位置的数组元素之和

计算一个数组中L位置到R位置的数组元素之和

解题思路一：

我们很容易想到遍历数组,遍历数组L位置到R位置的元素并相机得到和

代码：

public class PreSum {

	public static class RangeSum1 {

		private int[] arr;

		public RangeSum1(int[] array) {
			arr = array;
		}
		//常规操作就是依次遍历L到R位置的元素并且相加得到和
		public int rangeSum(int L, int R) {
			int sum = 0;
			for (int i = L; i <= R; i++) {
				sum += arr[i];
			}
			return sum;
		}

	}

解题思路二：

我们可以选择重新定义一个数组作为前缀数组之和,这个数组记录每一位数组元素与之前面数组元素之和,这样如果是计算原来数组的0-R位置的数组元素之和只需要返回前缀数组的R位置元素即可,当要计算原来数组的L-R位置元素数组之和只需要返回前缀数组的R位置元素-L-1位置元素的差即可得到。

代码：

/**
 * 目的：计算一个数组的l到r位置的数组元素之和
 * 方法：定义一个与原来数组等长的数组作为前缀和数组
 */
public class PreSumArray {
    public static class RangeSum{
        public static void preSumArray(int[] array){
            //1.记录数组的长度
            int length = array.length;
            //2.定有一个与原来数组等长的数组
            int[] preSum = new int[length];
            //2.1原来数组的第一位赋值给新数组的第一位
            preSum[0] = array[0];
            //3.循环原来的数组并且与现在数组的i-1位置的元素与原来数组的i位置的元素相加
            for (int i = 1; i < length; i++) {
                preSum[i] = preSum[i-1] + array[i];
            }
            //至此在新的数组中就记录了原来数组的数组元素之和
        }

        public int rangeArraySum(int[] preSum,int l,int r){
            return l == 0 ? preSum[r]:preSum[r] - preSum[l - 1];
        }
    }
}