Table of Contents

# Arithmetic Slices II – Subsequence – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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,`

.,4,1,__2__,**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:7Explanation: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:16Explanation:Any subsequence of this array is arithmetic.

**Constraints:**

`1 <= nums.length <= 1000`

`-2`

^{31}<= nums[i] <= 2^{31}- 1

# C++ Arithmetic Slices II – SubsequenceLeetCode Solution

class Solution {

public:

int numberOfArithmeticSlices(vector<int> &nums) {

int n = nums.size();

int ans = 0;

vector<unordered_map<long long, int>> dp(n); // dp[i][d]

for (int i = 1; i < n; i++) {

for (int j = 0; j < i; j++) {

long long diff = (long long) nums[i] – nums[j];

int cnt = dp[j].count(diff) ? dp[j][diff] : 0;

dp[i][diff] += cnt + 1;

ans += cnt;

}

}

return ans;

}

};

# Java Arithmetic Slices II – Subsequence LeetCode Solution

class Solution {

public int numberOfArithmeticSlices(int[] nums) {

int n = nums.length;

int ans = 0;

HashMap<Long, 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] – (long) nums[j];

int cnt = dp[j].getOrDefault(diff, 0);

dp[i].put(diff, dp[i].getOrDefault(diff, 0) + cnt + 1);

ans += cnt;

}

}

return ans;

}

}

# Python 3 Arithmetic Slices II – Subsequence LeetCode Solution

class Solution:

def numberOfArithmeticSlices(self, nums: List[int]) -> int:

n = len(nums)

dp = [defaultdict(int) for _ in range(n)]ans = 0

for i in range(1, n):

for j in range(i):

diff = nums[i] – nums[j]

cnt = 0

if diff in dp[j]:

cnt = dp[j][diff]dp[i][diff] += cnt + 1

ans += cntreturn ans

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1