数组区间

303. Range Sum Query - Immutable (Easy)

题目描述
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], … , nums[j])）
示例
输入：
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]
解释：
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))

暴力法

class NumArray {
    int[] array;
    public NumArray(int[] nums) {
        array = nums;
    }
    public int sumRange(int i, int j) {
        i = Math.max(0,i);
        j = Math.min(j,array.length-1);
        int sum = 0;
        for(int x=i; x<=j; x++){
            sum = array[x] + sum;
        }
        return sum;
    }
}

动态规划

思路 ：构造数组时计算前n项和。

class NumArray {
    int[] array;
    public NumArray(int[] nums) {
        array = nums;
        for(int i=1; i<nums.length; i++){
            array[i] = array[i-1] + array[i];
        }
    }
    public int sumRange(int i, int j) {
        if(i==0){
            return array[j];
        }else{
            return array[j]-array[i-1];
        }
    }
}

结果

413. Arithmetic Slices (Medium)

题目描述
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P满足以下条件，则称子数组(P, Q)为等差数组：元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。函数要返回数组 A 中所有为等差数组的子数组个数。
示例
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

暴力

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int len = A.length;
        if(len<3){
            return 0;
        }
        int count = 0;
        for(int i=0; i<len-2; i++){
            int cha = A[i+1]-A[i];
            for(int j=i+2; j<len; j++){
                if(A[j]-A[j-1]==cha){
                    count++;
                }else{
                    break;
                }
            }
        }
        return count;
    }
}

动态规划

思路 dp[i]表示以i结尾的等差数列个数

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int len = A.length;
        if(len<3){
            return 0;
        }
        int[] dp = new int[len];
        for(int i=2; i<len; i++){
            if(A[i]-A[i-1] == A[i-1]-A[i-2]){
                dp[i] = dp[i-1]+1;
            }
        }
        int total = 0;
        for(int i=2; i<len; i++){
            total = total + dp[i];
        }
        return total;
    }
}