HackMD
446.Arithmetic Slices II - Subsequence
tags: Hard,Array,DP
446. Arithmetic Slices II - Subsequence
題目描述
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 <= 1000nums[i]<=
解答
C++
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
vector<unordered_map<long long, int>> dp(n);
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i-1; j >= 0; j--) {
long long diff = (long long)nums[i] - (long long)nums[j];
ans += dp[j][diff];
dp[i][diff] += dp[j][diff] + 1;
}
}
return ans;
}
};
Yen-Chi ChenSun, Nov 27, 2022 8:49 PM
Python
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]
ans += dp[j][diff]
dp[i][diff] += dp[j][diff] + 1
return ans
Yen-Chi ChenSun, Nov 27, 2022 8:49 PM
Time:
Extra Space:
