Last Updated on 2022-11-28 by Clay
題目
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
題目會給定一組整數數列，該數列是固定由小到大排序的。我們要返回在這個數列中，所有等差數列的組合數。
解題思路
這題我本來寫了一個超暴力解，然後很理所當然地 TLE 了。所以只能參考一下大神的解法，發現用 DP 解非常有效。
這次 DP 雖然看似是一維的，但卻得用 hash map 的方式去儲存。key 是距離、value 是次數。
首先我們從第二個數值開始，一直去計算左邊的數字跟自己之間的差距。而且如果計算差距的數值底下，有跟當前的差距一樣的 hash map key 值，則也要把該 key 值的數值加到當前數值的 hash map 底下。
就拿第一個範例來說：
2 左邊沒有任何數，所以忽略不計。
4 左邊只有 2 一個數值，所以差距 2，次數 1 次。
6 左邊有 2 跟 4，跟 2 差距 4，次數 1 次。
但是 6 跟 4 之間的差距為 2，而且 4 底下本來就紀錄有跟 2 之間的差距為 2！ => 這時候，我們就要把 6 底下的 hash map 多記錄成 2: 2
| 2 | 4 | 6 | 8 | 10 |
|---|---|---|---|---|
| 2: 1 | 4: 1 | |||
| 2: 2 |
依此類推，我們完成這張 DP 表。
| 2 | 4 | 6 | 8 | 10 |
|---|---|---|---|---|
| 2: 1 | 4: 1 | 6:1 | 8:1 | |
| 2: 2 | 4:1 | 6:1 | ||
| 2:3 | 4:2 | |||
| 2:4 |
實際變化可以表示成下圖：
| 2: 2 | [2, 4, 6] |
| 2: 3 | [2, 4, 6, 8] [4, 6, 8] |
| 4: 2 | [2, 6, 8] |
| 2: 4 | [2, 4, 6, 8, 10] [4, 6, 8, 10] [6, 8, 10] |
然後我們會注意到一個規律：只有在對應的差距次數 hash map 有被之前的值更新時才需要計算組合數，所以我們程式可以很直接地在更新時直接加上前一個差距數底下對應 key 值的 value。
詳細還請看程式碼。
C++ 範例程式碼
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
// Init
int results = 0;
vector<unordered_map<int, int>> dp(nums.size());
// Count
for (int i=0; i<nums.size(); ++i) {
for (int j=0; j<i; ++j) {
// 32 bit limit
long longDiff = (long)nums[i] - nums[j];
if (longDiff > INT_MAX || longDiff < INT_MIN) {
continue;
}
// Records
int intDiff = (int)longDiff;
++dp[i][intDiff];
if (dp[j].count(intDiff)) {
results += dp[j][intDiff];
dp[i][intDiff] += dp[j][intDiff];
}
}
}
return results;
}
};Python 範例程式碼
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
# Init
results = 0
dp = [{} for _ in range(len(nums))]
INT_MAX = 2147483647
INT_MIN = -2147483648
# Count
for i in range(len(nums)):
for j in range(i):
# 32 bit limit
diff = nums[i] - nums[j]
if diff > INT_MAX or diff < INT_MIN:
continue
# Records
dp[i][diff] = dp[i].get(diff, 0) + 1
if diff in dp[j]:
results += dp[j][diff]
dp[i][diff] += dp[j][diff]
return results