LeetCode | 303 RangeSumQueryImmutable

https://github.com/dolphinmind/datastructure/tree/datastructure-array-02

分析

• 所求解的区间[left,right]具有连续性，执行常规for循环计算，[0,left-1]的区间元素累加和 与[0, right]的区间元素累加和，有重复的运算区间[0,left)。累加和与长跑比赛其实一致，求取[left,right]区间的累计和，看做求取两者之间的距离差

• 倘若使用for循环频繁调用累加和计算，可以加一层缓存，用空间换取运算时间，即记录任意情况下left和right累积跑过的路程，两者相减即可

• 前缀和数组preSum[0]=0可以接收输入的nums 数组为空

• 同时思考前缀和数组的还原

主类

package com.github.dolphinmind.array;

/**
 * @author dolphinmind
 * @ClassName RangeSumQueryImmutable
 * @description 303. 区域和检索 - 数组不可变
 * @date 2024/8/2
 */

public class RangeSumQueryImmutable {

    // 前缀和数组 缓存概念
    private int[] preSum;
    private int[] recoverArray;
    private int length;

    public RangeSumQueryImmutable(int[] nums) {
        length = nums.length;

        // 初始化前缀和数组 preSum[0]=0
        preSum = new int[length + 1];

        // 初始化恢复数组 recoverArray
        recoverArray = new int[length];

        for (int i = 1; i < preSum.length; i++) {
            preSum[i] = preSum[i-1] + nums[i-1];
        }

    }

    public int sumRange(int left, int right) {

        if (left < 0 || right >= preSum.length - 1) {
            System.out.print("索引超出数组范围: ");
            return -1;
        }

        if (left == right) {
            System.out.print("索引相同: ");
            return 0;
        }

        if (left > right) {
            System.out.print("索引顺序错误: ");
            return preSum[left+1] - preSum[right];
        }

        System.out.print("索引顺序正确: ");
        return preSum[right + 1] - preSum[left];

    }

    public void recoverArray() {
        for (int i = length-1 ; i >= 0; i--) {
            recoverArray[i] = preSum[i+1]-preSum[i];
        }
    }

    public void printArray(int[] nums) {
        System.out.println();

        System.out.print("[");
        for (int item : nums) {
            System.out.print(item + " ");
        }
        System.out.print("]");
    }

    public void printOriginArray(int[] nums) {
        System.out.print("\n原始数组：");
        printArray(nums);
    }
    public void printPreSum() {
        System.out.print("\n前缀和数组：");
        printArray(preSum);
    }

    public void printRecoverArray() {
        this.recoverArray();
        System.out.print("\n复原数组: ");
        printArray(recoverArray);
    }
}

测试类

package com.github.dolphinmind.array;

import org.junit.Test;

/**
 * @author dolphinmind
 * @ClassName RangeSumQueryImmutableTest
 * @description
 * @date 2024/8/2
 */

public class RangeSumQueryImmutableTest {

    @Test
    public void test_sunRange() {
//        int[] nums = {-2, 0, 3, -5, 2, -1};
//        int[] nums   =  {   1, 2, 3, 4,  5,  6,  7,  8};
        int[] nums   = {};

        RangeSumQueryImmutable rangeSumQueryImmutable = new RangeSumQueryImmutable(nums);

        rangeSumQueryImmutable.printOriginArray(nums);
        rangeSumQueryImmutable.printPreSum();
        rangeSumQueryImmutable.printRecoverArray();

        System.out.println("\n");
        System.out.println(rangeSumQueryImmutable.sumRange(2, 2));
        System.out.println(rangeSumQueryImmutable.sumRange(0, 1));
        System.out.println(rangeSumQueryImmutable.sumRange(1, 0));
        System.out.println(rangeSumQueryImmutable.sumRange(1, 9));
        System.out.println(rangeSumQueryImmutable.sumRange(0, 7));

    }
}