Problem

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

Example 1

1
2
3

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.

Example 2

1
2

Input: nums = [1]
Output: 0

Solution

Method 1 – Dynamic Programming

Intuition

The key idea is that if three consecutive numbers form an arithmetic sequence, then any extension of this sequence by one element (with the same difference) also forms an arithmetic slice. We can use dynamic programming to count the number of arithmetic slices ending at each index.

Approach

  1. Initialize a variable ans to store the total count of arithmetic slices.
  2. Use a variable dp (or an array) to store the number of arithmetic slices ending at the current index.
  3. Iterate through the array starting from index 2.
  • For each index i, check if nums[i] - nums[i-1] == nums[i-1] - nums[i-2].
  • If true, increment dp by 1 (or set dp[i] = dp[i-1] + 1 if using an array), and add dp to ans.
  • If false, reset dp to 0.
  1. Return ans as the result.

This approach ensures that all possible arithmetic slices of length ≥ 3 are counted efficiently.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
   int numberOfArithmeticSlices(vector<int>& nums) {
      int n = nums.size(), ans = 0, dp = 0;
      for (int i = 2; i < n; ++i) {
        if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
           dp += 1;
           ans += dp;
        } else {
           dp = 0;
        }
      }
      return ans;
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func numberOfArithmeticSlices(nums []int) int {
   n, ans, dp := len(nums), 0, 0
   for i := 2; i < n; i++ {
      if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
        dp++
        ans += dp
      } else {
        dp = 0
      }
   }
   return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
   public int numberOfArithmeticSlices(int[] nums) {
      int n = nums.length, ans = 0, dp = 0;
      for (int i = 2; i < n; i++) {
        if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
           dp++;
           ans += dp;
        } else {
           dp = 0;
        }
      }
      return ans;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
   fun numberOfArithmeticSlices(nums: IntArray): Int {
      var ans = 0
      var dp = 0
      for (i in 2 until nums.size) {
        if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
           dp += 1
           ans += dp
        } else {
           dp = 0
        }
      }
      return ans
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
   def numberOfArithmeticSlices(self, nums: list[int]) -> int:
      n: int = len(nums)
      ans: int = 0
      dp: int = 0
      for i in range(2, n):
        if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
           dp += 1
           ans += dp
        else:
           dp = 0
      return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
   pub fn number_of_arithmetic_slices(nums: Vec<i32>) -> i32 {
      let n = nums.len();
      let mut ans = 0;
      let mut dp = 0;
      for i in 2..n {
        if nums[i] - nums[i-1] == nums[i-1] - nums[i-2] {
           dp += 1;
           ans += dp;
        } else {
           dp = 0;
        }
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(N) where N is the length of the array.
  • 🧺 Space complexity: O(1) (no extra space except variables).