区域和检索 - 数组不可变

• 一、题目描述
• 二、难度
• 三、示例
• 四、代码
• • Java版
  • • 4.1 法一：暴力法
    • 4.2 法二：前缀和法

一、题目描述

二、难度

简单

三、示例

四、代码

Java版

4.1 法一：暴力法

直接暴力解法，时间复杂度:O(n)

package per.Kidd.demo;import java.util.Arrays;import java.util.Scanner;/** * @author Kidd * @create 2022-04-14 18:22 *//* *  303. 区域和检索 - 数组不可变 *      法一：暴力法 *    时间复杂度:O(n) */public class NumArray {    private int[] nums;    //使用数组 nums 初始化对象    public NumArray(int[] nums) { this.nums = nums;    }    //返回数组 nums 中索引 left 和 right 之间的元素的总和,包含 left 和 right 两点    public int sumRange(int left, int right) { int sum = 0; for(int i = left; i <= right; ++i) {     sum += nums[i]; } return sum;    }    public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next().toString(); //获取字符串中的每一个数字 String[] arr = str.split(","); //创建一个int类型的数组 int[] nums = new int[arr.length]; //将字符串数组转为int数组 for(int i = 0; i < arr.length; ++i) {     nums[i] = Integer.parseInt(arr[i]); } NumArray numArray = new NumArray(nums); int left = in.nextInt(), right = in.nextInt(); System.out.println(numArray.sumRange(left, right)); in.close();    }}

4.2 法二：前缀和法

前缀和法，时间复杂度为 O(1)
利用一个成员变量数组专门记录前n个数之和

package per.Kidd.demo;import java.util.Arrays;import java.util.Scanner;/** * @author Kidd * @create 2022-04-14 18:22 *//* *  303. 区域和检索 - 数组不可变   -2,0,3,-5,2,-1 *      法二：前缀和法 *    时间复杂度:O(1) */public class NumArray {    //记录前n个数之和    private int[] preNsum;    //使用数组 nums 初始化对象    public NumArray(int[] nums) { //分配空间并初始化为0 preNsum = new int[nums.length + 1]; //累加 for(int i = 0; i < nums.length; ++i) {     //preNsum[k]表示存放前k个数之和     preNsum[i + 1] = preNsum[i] + nums[i]; }    }    //返回数组 nums 中索引 left 和 right 之间的元素的总和,包含 left 和 right 两点    public int sumRange(int left, int right) { //下标[left,right]元素之和=前right+1元素之和 - 前left元素之和(因包含端点元素，故不是前left+1元素之和) return preNsum[right + 1] - preNsum[left];    }    public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next().toString(); //获取字符串中的每一个数字 String[] arr = str.split(","); //创建一个int类型的数组 int[] nums = new int[arr.length]; //将字符串数组转为int数组 for(int i = 0; i < arr.length; ++i) {     nums[i] = Integer.parseInt(arr[i]); } NumArray numArray = new NumArray(nums); int left = in.nextInt(), right = in.nextInt(); System.out.println(numArray.sumRange(left, right)); in.close();    }}