小算法~（一个数组查找 数组索引范围 值的总和 ）

package find;

/** 返回 数组范围和
 * 第一种方法明显在空间上节省不少，但是却多了一步 减的操作
 * 第二种方法在空间上多了很多，但是如果在取出数组范围和达到一定量级
 * 量变引起质变，第二种就会比第一种好
 * @author codelmh
 * @data 2021/12/5
 */
public class FindRangeSum {
    public static void main(String[] args) {
        int[] arr = {1, 5, 9, 4, 6, 10, 2};
        System.out.println(sumRange1(arr, 0, 2));
    }

    /**
     *  用一个一维数组(h[arr.length])存储数组的 0~当前下标的和
     *  如果要返回范围则 只需要 h[right] - h[left] 就能得到
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int sumRange1(int[] arr, int left, int right){
        int[] h = new int[arr.length];
        h[0] = arr[0];
        for (int i = 1; i < arr.length; i++){
            h[i] = h[i - 1] + arr[i];
        }
        for (int j = 0; j < arr.length; j++){
            System.out.print(h[j]+" ");
        }
        if (left == 0 && right == arr.length-1) {
            return h[arr.length-1];
        }
        return  h[right]-h[left];
    }

    /**
     * 用一个二维数组(newArr[][])来存储每一个范围查询的值 如果需要取left ~ right范围的和
     * 则直接从二维数组 取 newArr[left][right]的值即可
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int sumRange2(int[] arr, int left, int right) {
        //定义一个存储每一个范围和的二维数组
        int[][] newArr = new int[arr.length][arr.length];
        for(int i = 0; i < arr.length; i++){
            for (int j = i; j < arr.length; j++){
                if ( i == j){
                    newArr[i][j] = arr[i];
                }else {
                    newArr[i][j] = newArr[i][j-1] + arr[j];
                }
            }
        }
        return newArr[left][right];
    }
}