---

303. 区域和检索 - 数组不可变

思路：前缀和

1.因为要根据给出的两个索引，来返回索引区间的和

2.创建一个n+1大小的新数组

3.遍历原本的数组，计算每个位置的前缀和

4.再通过给出的索引下标，在新数组中，找到两个索引的前缀和

5.返回两者的差值

6.left位置的前缀和，不包含left。right位置的前缀和，不包含right。所以要right+1

代码：

    public  NumArray(int[] nums) {
        int n = nums.length;
        sum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }


    public int sumRange(int left, int right) {

        return sum[right + 1] - sum[left];
    }

点击移步博客主页，欢迎光临~