In this **Leetcode Arithmetic Slices II - Subsequence problem solution** you have 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 a 32-bit integer.

## Problem solution in Python.

class Solution: def numberOfArithmeticSlices(self, A: List[int]) -> int: dic={} for i in range(len(A)): dic[i]={} ans=0 for i in range(len(A)): for j in range(i): d=A[i]-A[j] if d not in dic[j]: if d in dic[i]: dic[i][d]+=1 else: dic[i][d]=1 else: if d not in dic[i]: dic[i][d]=dic[j][d]+1 ans+=dic[j][d] else: dic[i][d]+=dic[j][d]+1 ans+=dic[j][d] return ans

## Problem solution in Java.

public int numberOfArithmeticSlices(int[] A) { int l = A.length; if(l <3){ return 0; int[] left = new int[l]; int[] right = new int[l]; left[0] = 0; right[l-1] = 0; for(int i=1;i<l;i++){ left[i] = A[i] - A[i-1]; } for(int i=l-2;i>=0;i--){ right[i] = A[i+1] - A[i]; } int prev = 0; int[] result = new int[l]; for(int i=1;i<l-1;i++){ if(right[i] == left[i]){ result[i] = 1; if(right[i-1] == left[i-1]){ result[i] = result[i]+result[i-1]; } } } int sum=0; for(int i=0;i<l;i++){ sum+=result[i]; } return sum; }

## Problem solution in C++.

class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { int ans = 0, n = size(nums); vector<unordered_map<int, int>> freq(n); for (size_t i = 0; i < n; ++i) { for (size_t ii = 0; ii < i; ++ii) { long temp = (long) nums[i] - nums[ii]; if (temp > INT_MAX || temp < INT_MIN) continue; int diff = nums[i] - nums[ii]; ans += freq[ii][diff]; freq[i][diff] += 1 + freq[ii][diff]; } } return ans; } };

## 0 Comments