0413 - Arithmetic Slices

0413 - Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

• For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences. Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

Examples

Input: nums = [1,2,3,4] Output: 3 Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself.

Input: nums = [1] Output: 0

Constraints

• 1 <= nums.length <= 5000

• -1000 <= nums[i] <= 1000

Java Solution (Dynammic Programming)

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