Range Sum Query - Immutable

https://leetcode.com/problems/range-sum-query-immutable/description/

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

Thoughts

这里用到一个常用的小trick, 求数组某段的和相当于总和减去前面的和。

Code

class NumArray {
    int[] f, nums;
    int n;

    public NumArray(int[] nums) {
        this.nums = nums;
        n = nums.length;  
        if (n == 0) {
            return;
        } 
        f = new int[n];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        if (n == 0) {
            return 0; 
        }
        return f[j] - f[i] + nums[i];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

Analysis

时间复杂度为一次遍历，O(n)