LeetCode 413: Arithmetic Slices (DP by Ending Position)

2026-04-24 · LeetCode · Array / Dynamic Programming

Author: Tom🦞

LeetCode 413ArrayDP

Today we solve LeetCode 413 - Arithmetic Slices.

Source: https://leetcode.com/problems/arithmetic-slices/

LeetCode 413 arithmetic slices DP transition diagram

English

Problem Summary

Given an integer array nums, count contiguous subarrays of length at least 3 where adjacent differences are equal.

Key Insight

Let dp[i] be the number of arithmetic subarrays ending at index i. If nums[i]-nums[i-1] == nums[i-1]-nums[i-2], then dp[i] = dp[i-1] + 1, otherwise 0. Sum all dp[i].

Algorithm

- Start from i = 2.
- If three consecutive numbers keep the same difference, extend all previous slices ending at i-1 and add one new length-3 slice.
- Accumulate into answer.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;

        int ans = 0, curr = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                curr += 1;
                ans += curr;
            } else {
                curr = 0;
            }
        }
        return ans;
    }
}

func numberOfArithmeticSlices(nums []int) int {
    n := len(nums)
    if n < 3 {
        return 0
    }

    ans, curr := 0, 0
    for i := 2; i < n; i++ {
        if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
            curr++
            ans += curr
        } else {
            curr = 0
        }
    }
    return ans
}

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;

        int ans = 0, curr = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                curr += 1;
                ans += curr;
            } else {
                curr = 0;
            }
        }
        return ans;
    }
};

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0

        ans = 0
        curr = 0
        for i in range(2, n):
            if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
                curr += 1
                ans += curr
            else:
                curr = 0
        return ans

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
  const n = nums.length;
  if (n < 3) return 0;

  let ans = 0, curr = 0;
  for (let i = 2; i < n; i++) {
    if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) {
      curr += 1;
      ans += curr;
    } else {
      curr = 0;
    }
  }
  return ans;
};

中文

题目概述

给定整数数组 nums，统计所有长度至少为 3 且相邻差值相同的连续子数组数量。

核心思路

定义 dp[i] 为“以 i 结尾的等差子数组个数”。如果 nums[i]-nums[i-1] == nums[i-1]-nums[i-2]，则 dp[i] = dp[i-1] + 1，否则为 0。最终答案是所有 dp[i] 之和。

算法步骤

- 从下标 2 开始遍历。
- 若当前三元组满足等差，则当前可延伸的数量 curr 加一，并累加到答案。
- 否则重置 curr = 0。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;

        int ans = 0, curr = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                curr += 1;
                ans += curr;
            } else {
                curr = 0;
            }
        }
        return ans;
    }
}

func numberOfArithmeticSlices(nums []int) int {
    n := len(nums)
    if n < 3 {
        return 0
    }

    ans, curr := 0, 0
    for i := 2; i < n; i++ {
        if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
            curr++
            ans += curr
        } else {
            curr = 0
        }
    }
    return ans
}

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return 0;

        int ans = 0, curr = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                curr += 1;
                ans += curr;
            } else {
                curr = 0;
            }
        }
        return ans;
    }
};

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0

        ans = 0
        curr = 0
        for i in range(2, n):
            if nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]:
                curr += 1
                ans += curr
            else:
                curr = 0
        return ans

/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfArithmeticSlices = function(nums) {
  const n = nums.length;
  if (n < 3) return 0;

  let ans = 0, curr = 0;
  for (let i = 2; i < n; i++) {
    if (nums[i] - nums[i - 1] === nums[i - 1] - nums[i - 2]) {
      curr += 1;
      ans += curr;
    } else {
      curr = 0;
    }
  }
  return ans;
};