20240106-算术切片 II - 子序列

题目要求

给定一个整数数组 nums，返回 nums 的所有算术子序列的个数。

如果一个数字序列至少由三个元素组成，且任意两个连续元素之间的差值相同，则该序列称为算术序列。

例如，[1, 3, 5, 7, 9]、[7, 7, 7]和[3, -1, -5, -9]都是算术序列。

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.

思路

使用了动态规划的方法，并且利用了哈希表（在C++中是map）来优化查找过程。

cnt数组的含义：

• cnt是一个向量，其长度等于输入数组nums的长度。每个元素cnt[i]是一个map，其中的键是等差（差值delta），值是到目前为止出现该等差的子序列个数。
• 对于每一对i和j（其中i > j），delta = nums[i] - nums[j]是nums[j]和nums[i]之间的差值。cnt[i][delta]记录了以nums[i]结尾，等差为delta的子序列数量。
• 每当找到一个新的差值delta时，我们在cnt[i][delta]中至少添加1，代表由nums[j]和nums[i]形成的长度为2的子序列。

如何更新cnt数组：

• 对于每个i（从1到n-1），遍历所有j（从0到i-1），计算delta。
• 如果cnt[j]中存在键为delta的项，则sum = cnt[j][delta]；这意味着在nums[j]之前已经存在等差为delta的子序列。
• 更新cnt[i][delta]。这里cnt[i][delta] += sum + 1的意思是，以nums[i]结尾的、等差为delta的子序列数量等于以nums[j]结尾的这些子序列数量（sum）加上新增的一个子序列（由nums[j]和nums[i]组成）。
• ans累加sum。sum代表的是找到的等差为delta且长度至少为3的子序列数量。

如何计算长度至少为3的序列：

• 当我们在位置i和j（i > j）找到一个等差delta时，如果cnt[j][delta]存在，这意味着在位置j之前已经有一个或多个长度至少为2的等差为delta的子序列。
• cnt[j][delta]的值是以nums[j]结尾的、等差为delta的子序列数量，但这里重要的是，这些子序列的长度都至少是2。当我们在cnt[i][delta]中添加cnt[j][delta]时，实际上是将这些长度至少为2的子序列扩展为长度至少为3的子序列（因为我们添加了nums[i]作为新的结尾元素）。

更新ans变量：

• 每当我们在cnt[i][delta]中添加cnt[j][delta]时，这些都是新生成的长度至少为3的等差序列。
• 因此，在更新ans时，我们只添加cnt[j][delta]的值。这样，ans最终就是所有长度至少为3的等差序列的总数。

代码

#define LL long long
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        LL ans = 0;
        vector<map<LL, int>> cnt(n);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                LL delta = (LL)nums[i] - (LL)nums[j];
                int sum = 0;
                if (cnt[j].find(delta) != cnt[j].end()) {
                    sum = cnt[j][delta];
                }
                cnt[i][delta] += sum + 1;
                // printf("%d %d %lld\n", i, cnt[i][delta], delta);
                ans += sum;
            }
        }
        return (int)ans;
    }
};

Complexity Analysis

• Time complexity :?O(n2)O(n ^ 2)O(n2). We can use double loop to enumerate all possible states.

• Space complexity :?O(n2)O(n ^ 2)O(n2). For each?i, we need to store at most?n?distinct common differences, so the total space complexity is?O(n2)O(n ^ 2)O(n2).

总结

代码是LC上的教程，动态规划的思想是有的，但是算法中不需要真正存储等差序列，只需要用数量代表总数，并且更新结果的这种方法值得学习。目前自己还写不出来。