Table of Contents
Problem Statement :
Arithmetic Slices II – Subsequence LeetCode Solution – Given an integer array of 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 32bit integer.
Example :
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]
Example 2
Input: nums = [7,7,7,7,7] Output: 16 Explanation: Any subsequence of this array is arithmetic.
Constraints :
Observation :

 To determine an arithmetic sequence, we need at least two parameters: the first element of the sequence, and the common difference.
 If the first term of an arithmetic sequence is a1 and the common difference of successive members is d, then the nth term of the sequence (an) is given by:
an = a1 + (n1)d
Approach :
 As we need to find the arithmetic subsequence i.e. elements of an array should be in arithmetic progression no matter they are contiguous or noncontiguous.

We will create an array of maps to store the frequency of difference of an element with respect to its previous elements.

In the original definition of arithmetic subsequence, the length of the subsequence must be at least 3. But we are defining new subsequences that are weak subsequences of only length 2.

frequencyArrayMap[i] stores the number of weak arithmetic subsequences that end with nums[i] and its common difference is diff.

A weak arithmetic sequence has two characteristics that we are defining:
 For any pair i,j (i != j) nums[i] and nums[j] can always form a weak arithmetic subsequence.
 If we add a new element to a weak arithmetic sequence, the new sequence must be an arithmetic sequence, because the new sequence has become the original arithmetic sequence of at least length 3.

Now for each nums[i], we will find the nums[j] forming a weak arithmetic sequence of length two.

For the nums[j], we will iterate from 0 to less than i.

In the FrequencyMapArray, which already stores the common difference of two elements nums[i] and nums[j], if we will find the same common difference for different pairs then we will add that frequency to our answer.
Code for Arithmetic Slices II – Subsequence :
Java Code :
class Solution { public int numberOfArithmeticSlices(int[] nums) { int n = nums.length; long ans = 0; Map<Integer, Integer>[] frequencyArrayMap = new Map[n]; for(int i=0;i<n;i++){ frequencyArrayMap[i]=new HashMap<>(); } for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ long commondiff = (long)nums[i](long)nums[j]; if(commondiff<Integer.MIN_VALUE  commondiff> Integer.MAX_VALUE)continue; int diff =(int)commondiff; int prevFreq=frequencyArrayMap[j].getOrDefault(diff,0); int currFreq=frequencyArrayMap[i].getOrDefault(diff,0); ans+=prevFreq; frequencyArrayMap[i].put(diff,prevFreq+currFreq+1); } } return (int)ans; } }
C++ Code :
#define LL long long class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { int n = nums.size(); LL ans = 0; vector<map<int,int>>frequencyArrayMap(n); for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ LL commondiff = (LL)nums[i](LL)nums[j]; if(commondiff<= INT_MIN  commondiff>= INT_MAX)continue; int diff =(int)commondiff; int prevFreq =0; int currFreq=0; if(frequencyArrayMap[j].find(diff) != frequencyArrayMap[j].end()){ prevFreq = frequencyArrayMap[j][diff]; currFreq = frequencyArrayMap[i][diff]; ans += prevFreq; frequencyArrayMap[i][diff] = currFreq + prevFreq + 1; } else{ frequencyArrayMap[i][diff]++; } } } return (int)ans; } };
Complexity Analysis for Arithmetic Slices II – Subsequence LeetCode Solution:
Time Complexity
O(n2)
, as we are using two loops.
Space Complexity
O(n2)
For each num [i], we need to store at most n
distinct common differences, so the total space complexity is $O(n^_{2}).$