Sponsored
Sponsored
This approach uses dynamic programming and hashmaps to calculate arithmetic subsequences efficiently. For each index, we maintain a hashmap that tracks the count of different differences (arithmetic differences) and the number of subsequences that end with that difference at the given index. This allows us to build potential subsequences as we iterate over the array.
Time Complexity: O(n^2), where n is the length of the input array.
Space Complexity: O(n * m), where m is the number of possible differences (limited by the constraint of 31-bit integer).
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6int numberOfArithmeticSlices(vector<int>& nums) {
7 int n = nums.size();
8 int total = 0;
9 vector<unordered_map<long, int>> dp(n);
10
11 for (int i = 0; i < n; ++i) {
12 for (int j = 0; j < i; ++j) {
13 long diff = (long)nums[i] - (long)nums[j];
14 int count_at_j = dp[j][diff];
15 dp[i][diff] += count_at_j + 1;
16 total += count_at_j;
17 }
18 }
19 return total;
20}
21
22int main() {
23 vector<int> nums = {2, 4, 6, 8, 10};
24 cout << numberOfArithmeticSlices(nums) << endl;
25 return 0;
26} This C++ solution uses `unordered_map` to manage differences, enabling fast insertion and searching for differences. For each pair `(j, i)`, where `j < i`, we calculate the difference `diff` and update the solution count involving that difference between subsequent indices.
This approach considers all possible subsequences (using combinations) and checks if each subsequence is arithmetic. Although not efficient, it can be used to demonstrate the logic on small arrays to understand the problem better.
Time Complexity: O(n * 2^n) for combinations, where n is length of `nums`.
Space Complexity: O(n) given additional space for combinations.
1
This Python solution directly generates combinations, checks their arithmetic property, and accumulates the count. The approach demonstrates brute-force searching across combination space, understandable but inefficiently scales poorly.