[LeetCode] 446. Arithmetic Slices II - Subsequence

[grandyang]

 

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, these are arithmetic sequences:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

 

A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N.

A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

The function should return the number of arithmetic subsequence slices in the array A.

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

 

Example:

Input: [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]

这道题是之前那道Arithmetic Slices的延伸，那道题比较简单是因为要求等差数列是连续的，而这道题让我们求是等差数列的子序列，可以跳过某些数字，不一定非得连续，那么难度就加大了，但还是需要用动态规划Dynamic Progrmming来做。知道用DP来做是一回事，真正能做出来又是另一回事。刷题的最终目的不是背题，而是训练思维方式，如何从完全没思路，变为好像有点思路，慢慢推理演变找出正确解，就像顺着藏宝图的丝丝线索最终发现了宝藏一样，是无比的令人激动和富有成就感的过程。死记硬背的话，只要题目稍稍变形一下就完蛋。这就是为啥博主喜欢看fun4LeetCode大神的帖子，虽然看范佛力扣大神的帖子像读论文，但是有推理过程，看完让人神清气爽，茶饭不思，燃鹅遇到同类型的还是不会，还是要再看。好，博主皮一下就行了，就不皮几万了，下面来顺着大神的帖子来讲吧。

好，既然决定要用DP了，那么首先就要确定dp数组的定义了，刚开始我们可能会考虑使用个一维的dp数组，然后dp[i]定义为范围为[0, i]的子数组中等差数列的个数。定义的很简单，OK，但是基于这种定义的状态转移方程却十分的难想。我们想对于(0, i)之间的任意位置j，如何让 dp[i] 和 dp[j] 产生关联呢？是不是只有 A[i] 和 A[j] 的差值diff，跟A[j]之前等差数列的差值相同，才会有关联，所以差值diff是一个很重要的隐藏信息Hidden Information，我们必须要在dp的定义中考虑进去。所以一维dp数组是罩不住的，必须升维，但是用二维dp数组的话，差值diff那一维的范围又是个问题，数字的范围是整型数，所以差值的范围也很大，为了节省空间，我们建立一个一维数组dp，数组里的元素不是数字，而是放一个HashMap，建立等差数列的差值和当前位置之前差值相同的数字个数之间的映射。我们遍历数组中的所有数字，对于当前遍历到的数字，又从开头遍历到当前数字，计算两个数字之差diff，如果越界了不做任何处理，如果没越界，我们让dp[i]中diff的差值映射自增1，因为此时A[i]前面有相差为diff的A[j]，所以映射值要加1。然后我们看dp[j]中是否有diff的映射，如果有的话，说明此时相差为diff的数字至少有三个了，已经能构成题目要求的等差数列了，将dp[j][diff]加入结果res中，然后再更新dp[i][diff]，这样等遍历完数组，res即为所求。

我们用题目中给的例子数组 [2，4，6，8，10] 来看，因为2之前没有数字了，所以我们从4开始，遍历前面的数字，是2，二者差值为2，那么在dp[1]的HashMap就可以建立 2->1 的映射，表示4之前有1个差值为2的数字，即数字2。那么现在i=2指向6了，遍历前面的数字，第一个数是2，二者相差4，那么在dp[2]的HashMap就可以建立 4->1 的映射，第二个数是4，二者相差2，那么先在dp[2]的HashMap建立 2->1 的映射，由于dp[1]的HashMap中也有差值为2的映射，2->1，那么说明此时至少有三个数字差值相同，即这里的 [2 4 6]，我们将dp[1]中的映射值加入结果res中，然后当前dp[2]中的映射值加上dp[1]中的映射值。这应该不难理解，比如当i=3指向数字8时，j=2指向数字6，那么二者差值为2，此时先在dp[3]建立 2->1 的映射，由于dp[2]中有 2->2 的映射，那么加上数字8其实新增了两个等差数列 [2,4,6,8] 和 [4,6,8]，所以结果res加上的值就是 dp[j][diff]，即2，并且 dp[i][diff] 也需要加上这个值，才能使得 dp[3] 中的映射变为 2->3 ，后面数字10的处理情况也相同，这里就不多赘述了，最终的各个位置的映射关系如下所示：

 

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,10]

2->4：[2,4,6,8,10]    [4,6,8,10]    [6,8,10]

 

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int res = 0, n = A.size();
        vector<unordered_map<int, int>> dp(n);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                long delta = (long)A[i] - A[j];
                if (delta > INT_MAX || delta < INT_MIN) continue;
                int diff = (int)delta;
                ++dp[i][diff];
                if (dp[j].count(diff)) {
                    res += dp[j][diff];
                    dp[i][diff] += dp[j][diff];
                }
            }
        }
        return res;
    }
};

 

类似题目：

Arithmetic Slices

 

参考资料：

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/solution/

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/discuss/92837/C++_DP_Accepted

https://leetcode.com/problems/arithmetic-slices-ii-subsequence/discuss/92822/Detailed-explanation-for-Java-O(n2)-solution

 

LeetCode All in One 题目讲解汇总(持续更新中...)