413. Arithmetic Slices

 一刷 06/2022

Version #1 DP with 1D array

Time O(N)

Space O(N)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Arithmetic Slices.

Memory Usage: 42.6 MB, less than 11.92% of Java online submissions for Arithmetic Slices.

class Solution {

    public int numberOfArithmeticSlices(int[] nums) {

        // number of arithmetic slice ending with nums[i]

        int[] dp = new int[nums.length];

        int sum = 0;

        for (int i = 0; i < nums.length; i++) {

            if (i < 2 || nums[i] - nums[i - 1] != nums[i - 1] - nums[i - 2]) {

                // dp[i] = 0; // can be ignore, since default is 0 already

                continue;

            }

            dp[i] = 1 + dp[i - 1];

            sum += dp[i];

        }

        return sum;

    }

}