Last updated on January 21st, 2025 at 02:20 am
Here, we see an Arithmetic Slices II Subsequence LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Companies
Baidu
Level of Question
Hard

Arithmetic Slices II Subsequence LeetCode Solution
Table of Contents
1. Problem Statement
Given an integer array nums
, return the number of all the arithmetic subsequences of nums
.
A sequence of numbers 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. - For example,
[1, 1, 2, 5, 7]
is not an arithmetic sequence.
A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.
- For example,
[2,5,10]
is a subsequence of[1,2,1,2,4,1,5,10]
.
The test cases are generated so that the answer fits in 32-bit integer.
Example 1:
Input: nums = [2,4,6,8,10]
Output: 7
Explanation: All arithmetic subsequence slices are: [2,4,6] [4,6,8] [6,8,10] [2,4,6,8] [4,6,8,10] [2,4,6,8,10] [2,6,10]
2. Coding Pattern Used in Solution
The coding pattern used in this code is “Dynamic Programming with Hash Maps”. The code uses dynamic programming to store intermediate results in hash maps (or dictionaries) to avoid redundant calculations and efficiently count the number of arithmetic slices.
3. Code Implementation in Different Languages
3.1 Arithmetic Slices II Subsequence C++
class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { int n = nums.size(); int total_count = 0; std::vector<std::unordered_map<int, int>> dp(n); for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { long long diff = static_cast<long long>(nums[i]) - nums[j]; if (diff > INT_MAX || diff < INT_MIN) continue; int diff_int = static_cast<int>(diff); dp[i][diff_int] += 1; if (dp[j].count(diff_int)) { dp[i][diff_int] += dp[j][diff_int]; total_count += dp[j][diff_int]; } } } return total_count; } };
3.2 Arithmetic Slices II Subsequence Java
class Solution { public int numberOfArithmeticSlices(int[] nums) { int n = nums.length; int total_count = 0; HashMap<Integer, Integer>[] dp = new HashMap[n]; for (int i = 0; i < n; ++i) { dp[i] = new HashMap<>(); } for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { long diff = (long) nums[i] - nums[j]; if (diff > Integer.MAX_VALUE || diff < Integer.MIN_VALUE) { continue; } int diffInt = (int) diff; dp[i].put(diffInt, dp[i].getOrDefault(diffInt, 0) + 1); if (dp[j].containsKey(diffInt)) { dp[i].put(diffInt, dp[i].get(diffInt) + dp[j].get(diffInt)); total_count += dp[j].get(diffInt); } } } return total_count; } }
3.3 Arithmetic Slices II Subsequence JavaScript
var numberOfArithmeticSlices = function(nums) { const n = nums.length; let total_count = 0; const dp = new Array(n).fill().map(() => new Map()); for (let i = 1; i < n; ++i) { for (let j = 0; j < i; ++j) { const diff = nums[i] - nums[j]; if (dp[j].has(diff)) { dp[i].set(diff, (dp[i].get(diff) || 0) + dp[j].get(diff)); total_count += dp[j].get(diff); } dp[i].set(diff, (dp[i].get(diff) || 0) + 1); } } return total_count; };
3.4 Arithmetic Slices II Subsequence Python
class Solution(object): def numberOfArithmeticSlices(self, nums): n = len(nums) dp = [[0] * n for _ in range(n)] map = {} for i in range(n): temp = nums[i] if temp not in map: map[temp] = [] map[temp].append(i) total_sum = 0 for i in range(1, n): for j in range(i + 1, n): a = 2 * nums[i] - nums[j] if a in map: for k in map[a]: if k < i: dp[i][j] += dp[k][i] + 1 else: break total_sum += dp[i][j] return total_sum
4. Time and Space Complexity
Time Complexity | Space Complexity | |
C++ | O(n²) | O(n²) |
Java | O(n²) | O(n²) |
JavaScript | O(n²) | O(n²) |
Python | O(n3) | O(n²) |