LeetCode - Easy - 303. Range Sum Query - Immutable

古城微笑少年丶 2022-10-28 10:10 26阅读 0赞

## Topic ##

*  Dynamic Programming

## Description ##

[https://leetcode.com/problems/range-sum-query-immutable/][https_leetcode.com_problems_range-sum-query-immutable]

Given an integer array `nums`, find the sum of the elements between indices `i` and `j` (`i ≤ j`), inclusive.

Implement the `NumArray` class:

*  `NumArray(int[] nums)` Initializes the object with the integer array nums.
 *  `int sumRange(int i, int j)` Return the sum of the elements of the nums array in the range `[i, j]` inclusive (i.e., `sum(nums[i], nums[i + 1], ... , nums[j])`)

**Example 1**:

Input
    ["NumArray", "sumRange", "sumRange", "sumRange"]
    [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
    Output
    [null, 1, -1, -3]
    
    Explanation
    NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
    numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
    numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
    numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

**Constraints**:

*  0 <= nums.length <= 10⁴
 *  \-10⁵ <= nums\[i\] <= 10⁵
 *  0 <= i <= j < nums.length
 *  At most 10⁴ calls will be made to sumRange.

## Analysis ##

略

## Submission ##

//我写的
    public class RangeSumQueryImmutable { 
    
    	private int[] sums;
    
    	public RangeSumQueryImmutable(int[] nums) { 
    		sums = new int[nums.length];
    		int sum = 0;
    		for (int i = 0; i < nums.length; i++) { 
    			sum += nums[i];
    			sums[i] = sum;
    		}
    
    	}
    
    	public int sumRange(int i, int j) { 
    		return sums[j] - (i == 0 ? 0 : sums[i - 1]);
    	}
    }
    
    // 别人写的
    class RangeSumQueryImmutable2 { 
    
    	private int[] sums;
    
    	public RangeSumQueryImmutable2(int[] nums) { 
    		for (int i = 1; i < nums.length; i++)
    			nums[i] += nums[i - 1];
    
    		this.sums = nums;
    	}
    
    	public int sumRange(int i, int j) { 
    		if (i == 0)
    			return sums[j];
    
    		return sums[j] - sums[i - 1];
    	}
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class RangeSumQueryImmutableTest { 
    
    	@Test
    	public void test() { 
    		RangeSumQueryImmutable obj = new RangeSumQueryImmutable(new int[] { -2, 0, 3, -5, 2, -1});
    
    		assertEquals(1, obj.sumRange(0, 2));
    		assertEquals(-1, obj.sumRange(2, 5));
    		assertEquals(-3, obj.sumRange(0, 5));
    	}
    
    	@Test
    	public void test2() { 
    		RangeSumQueryImmutable2 obj = new RangeSumQueryImmutable2(new int[] {  -2, 0, 3, -5, 2, -1 });
    
    		assertEquals(1, obj.sumRange(0, 2));
    		assertEquals(-1, obj.sumRange(2, 5));
    		assertEquals(-3, obj.sumRange(0, 5));
    	}
    }

[https_leetcode.com_problems_range-sum-query-immutable]: https://leetcode.com/problems/range-sum-query-immutable/