Last updated on October 6th, 2024 at 08:34 pm

Here, We see Arithmetic Slices II Subsequence LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Arithmetic Slices II Subsequence LeetCode Solution

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]

1. Arithmetic Slices II Subsequence LeetCode Solution 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;        
    }
};

2. Arithmetic Slices II Subsequence LeetCode Solution 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. Arithmetic Slices II Subsequence LeetCode Solution 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;
};

4. Arithmetic Slices II Subsequence LeetCode Solution 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