Ref: link

303. Range Sum Query - Immutable (Easy)

An easy problem. We can use dp to solve this problem. dp[i] means the sum of first i values. The dp formula is very obvious. dp[i] = dp[i-1] + nums[i-1]. If we need sum(2,5), we return dp[6] - dp[2]. dp[6] means the sum of first 6 values. dp[2] means the sum of first 2 values. dp[6] - dp[2] is the sum of values between the third and sixth value.

Time complexity is O(n). Space complexity is O(n). Here is the link.

class NumArray {
    
    private int dp[];
    
    public NumArray(int[] nums) {
        dp = new int[nums.length+1];
        for(int i=1;i<nums.length+1;i++){
            dp[i] =dp[i-1]+nums[i-1];
        }
    }
    
    public int sumRange(int i, int j) {
        return dp[j+1] - dp[i];
    }
}

413. Arithmetic Slices (Medium)

This problem is a little difficult. I didn’t come up with correct dp formula for a long time. The reason is I didn’t notice one trick. The trick is how many sub-arrays of a specific length are in an array. For example, we have an array with length 5. We need to find all sub arrays of length larger or equal than 3. We know the answer is 6. We can use the below code to find the answer:

pre = 0;
ans = 0;
for(int i =2;i<A.length;i++){
    pre++;
    ans+=pre;
}

Now, we know how to find sub arrays of target length in an array. The next problem is find Arithmetic Slices. We can use dp to solve this problem. dp[i] is used to store the number of arithmetic slices possible in the range (k,i) and not in any range (k,j) such that j<i. Again, k refers to the minimum index possible such that (k,j) constitutes a valid Arithmetic Slice. dp formula is dp[i] = dp[i-1] + 1 if this element satsfies the common difference criteria with the previous element. And we only need dp[i-1] to determine dp[i], so we can use a variable to represent the value.

We only need to consider about A[i], A[i-1], A[i-2] and d[i-1]. We don’t need to care about d[i-3], because the situation of dp[i-3] is represented by dp[i-1].

Time complexity is O(n). Space complexity is O(1). Here is the link.

    public int numberOfArithmeticSlices(int[] A) {
        int ans = 0;
        int pre = 0;
        for(int i =2;i<A.length;i++){
            if(A[i]-A[i-1]==A[i-1]-A[i-2]){
                pre++;
                ans+=pre;
            }
            else{
                pre = 0;
            }
        }
        return ans;
    }