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,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]
Example 2:
Input: nums = [7,7,7,7,7] Output: 16 Explanation: Any subsequence of this array is arithmetic.
Constraints:
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 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 += cnt
return 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
