LeetCode 446 - Arithmetic Slices II - Subsequence

Related: LeetCode 413 - Arithmetic Slices
https://leetcode.com/problems/arithmetic-slices-ii-subsequence/

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]

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

At first glance of the problem description, I had a strong feeling that the solution to the original problem can be built through its subproblems, i.e., the total number of arithmetic subsequence slices of the whole input array can be constructed from those of the subarrays of the input array. While I was on the right track to the final solution, it's not so easy to figure out the relations between the original problem and its subproblems.

To begin with, let's be ambitious and reformulate our problem as follows: let T(i) denote the total number of arithmetic subsequence slices that can be formed within subarray A[0, i], where A is the input array and 0 <= i < n with n = A.length. Then our original problem will be T(n - 1), and the base case is T(0) = 0.

To make the above idea work, we need to relate T(i) to all T(j) with 0 <= j < i. Let's take some specific j as an example. If we want to incorporate element A[i] into the subarray A[0, j], what information do we need? As far as I can see, we need to know at least the total number of arithmetic subsequence slices ending at each index k with difference d where 0 <= k <= j and d = A[i] - A[k], (i.e., for each such slice, its last element is A[k] and the difference between every two consecutive elements is d), so that adding A[i] to the end of each such slice will make a new arithmetic subsequence slice.

However, our original formulation of T(i) says nothing about the the total number of arithmetic subsequence slices ending at some particular index and with some particular difference. This renders it impossible to relate T(i) to all T(j). As a rule of thumb, when there is difficulty relating original problem to its subproblems, it usually indicates something goes wrong with your formulation for the original problem.

From our analyses above, each intermediate solution should at least contain information about the total number of arithmetic subsequence slices ending at some particular index with some particular difference. So let's go along this line and reformulate our problem as T(i, d), which denotes the total number of arithmetic subsequence slices ending at index i with difference d. The base case and recurrence relation are as follows:

1. Base case: T(0, d) = 0 (This is true for any d).
2. Recurrence relation: T(i, d) = summation of (1 + T(j, d)) as long as 0 <= j < i && d == A[i] - A[j].

For the recurrence relation, it's straightforward to understand the T(j, d) part: for each slice ending at index j with difference d == A[i] - A[j], adding A[i] to the end of the slice will make a new arithmetic subsequence slice, therefore the total number of such new slices will be the same as T(j, d). What you are probably wondering is: where does the 1 come from?

The point here is that to make our recurrence relation work properly, the meaning of arithmetic subsequence slice has to be extended to include slices with only two elements (of course we will make sure these "phony" slices won't contribute to our final count). This is because for each slice, we are adding A[i] to its end to form a new one. If the original slice is of length two, after adding we will have a valid arithmetic subsequence slice with three elements. Our T(i, d) will include all these "generalized" slices. And for each pair of elements (A[j], A[i]), they will form one such "generalized" slice (with only two elements) and thus contribute to one count of T(i, d).

Before jumping to the solution below, I'd like to point out that there are actually overlapping among our subproblems (for example, both T(i, d) and T(i + 1, d) require knowledge of T(j, d) with 0 <= j < i). This necessitates memorization of the intermediate results. Each intermediate result is characterized by two integers: i and d. The former is bounded (i.e., 0 <= i < n) since they are the indices of the element in the input array while the latter is not as d is the difference of two elements in the input array and can be any value. For bounded integers, we can use them to index arrays (or lists) while for unbounded ones, use of HashMap would be more appropriate. So we end up with an array of the same length as the input and whose element type is HashMap.

Here is the Java program (with a quick explanation given at the end). Both time and space complexity are O(n^2). Some minor points for improving time and space performance are:

1. Define the type of the difference as Integer type instead of Long. This is because there is no valid arithmetic subsequence slice that can have difference out of the Integer value range. But we do need a long integer to filter out those invalid cases.
2. Preallocate the HashMap to avoid reallocation to deal with extreme cases.
3. Refrain from using lambda expressions inside loops.

public int numberOfArithmeticSlices(int[] A) {
    int res = 0;
    Map<Integer, Integer>[] map = new Map[A.length];
  
    for (int i = 0; i < A.length; i++) {
        map[i] = new HashMap<>(i);
         
        for (int j = 0; j < i; j++) {
            long diff = (long)A[i] - A[j];
            if (diff <= Integer.MIN_VALUE || diff > Integer.MAX_VALUE) continue;
          
            int d = (int)diff;
            int c1 = map[i].getOrDefault(d, 0);
            int c2 = map[j].getOrDefault(d, 0);
            res += c2;
            map[i].put(d, c1 + c2 + 1);
        }
    }
  
    return res;
}

Quick explanation:

1. res is the final count of all valid arithmetic subsequence slices; map will store the intermediate results T(i, d), with iindexed into the array and d as the key of the corresponding HashMap.
2. For each index i, we find the total number of "generalized" arithmetic subsequence slices ending at it with all possible differences. This is done by attaching A[i] to all slices of T(j, d) with j less than i.
3. Within the inner loop, we first use a long variable diff to filter out invalid cases, then get the counts of all valid slices (with element >= 3) as c2 and add it to the final count. At last we update the count of all "generalized" slices for T(i, d) by adding the three parts together: the original value of T(i, d), which is c1 here, the counts from T(j, d), which is c2 and lastly the 1 count of the "two-element" slice (A[j], A[i]).

http://www.cnblogs.com/grandyang/p/6057934.html

这道题是之前那道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]

https://blog.csdn.net/u013007900/article/details/53321398
这道题难度不算特别大，因为看得出来肯定是dp题。因为，一个等差序列里面有好几个小的等差序列。
例如，2 4是一个等差序列，2 4 6是一个等差序列。
所以我们发现等差序列是可以扩展的。

那么就得到了，咱们的转移方程的一部分
dp[i][]=dp[j][delta]+1
dp[i][]=dp[j][delta]+1

其中i，j是表示该数在原序列中的位置,+1表示的是A[i]本身。
然后，因为A[i]这个数可能存在多个前缀序列，所以j的范围应该是[0,i-1]。

从而得到转移方程

dp[i][delta]=∑dp[j][delta]+1
dp[i][delta]=∑j=0n−1dp[j][delta]+1
写代码的时候注意一下，delta的范围比较大，为[−231,231−1][−231,231−1]。所以不能用一般的二维数组，用C++的话，估计要用map，用python的话要用元组
http://blog.csdn.net/gqk289/article/details/62218365

1.     public int numberOfArithmeticSlices(int[] A) {  
2.         int res = 0;  
3.         HashMap<Integer, Integer>[] map = new HashMap[A.length];  
4.         for (int i = 0; i < A.length; i++) {  
5.             map[i] = new HashMap();  
6.             for (int j = 0; j < i; j++) {  
7.                 long diff = (long)A[i] - A[j];  
8.                 if (diff > Integer.MAX_VALUE || diff < Integer.MIN_VALUE) {  
9.                     continue;  
10.                 }  
11.                 int d = (int)diff;  
12.                 int c1 = map[i].getOrDefault(d, 0);  
13.                 int c2 = map[j].getOrDefault(d, 0);  
14.                 // c2保存以A[j]为尾，gap为d的数组个数，如果把A[i]加到A[j]后面，  
15.                 // 那么以A[j]为尾，gap为d的数组个数也是c2  
16.                 res += c2;  
17.                 map[i].put(d, c1 + c2 + 1);  
18.             }  
19.         }  
20.         return res;  
21.     }  

http://blog.jerkybible.com/2016/11/16/LeetCode-446-Arithmetic-Slices-II-Subsequence/

使用动态规划来解这道题。假设dp[i][j]表示以A[i]结尾的子序列(P0, P1, …, Pi)构成的数列，序列中的元素之差为j。而dp[i][j]=dp[k][j]>0?dp[k][j]+1:1，0<=i<A.length()，0<=k<i。其中dp[k][j]为0的时候需要加1，也就是仅存在两个数的数列时dp[i][j]需要加1，这是因为再之后第3个数匹配时可以形成一个正确数列，然后1加到总数里。

public int numberOfArithmeticSlices(int[] A) { int re = 0; HashMap<Integer, HashMap<Long, Integer>> diffMaps = new HashMap<>(); for (int i = 0; i < A.length; i++) { HashMap<Long, Integer> diffMap = new HashMap<>(); diffMaps.put(i, diffMap); int num = A[i]; for (int j = 0; j < i; j++) { if ((long) num - A[j] > Integer.MAX_VALUE) continue; if ((long) num - A[j] < Integer.MIN_VALUE) continue; long diff = (long) num - A[j]; int count = diffMaps.get(j).getOrDefault(diff, 0); diffMaps.get(i).put(diff, diffMaps.get(i).getOrDefault(diff, 0) + count + 1); re += count; } } return re; }

http://bookshadow.com/weblog/2016/11/06/leetcode-arithmetic-slices-ii-subsequence/

如果一组长度至少为3的数，两两连续元素之差都相等，则称其为等差数列。

给定包含N个元素，起始下标为0的数组A。子序列切片是指任意整数序列(P0, P1, ..., Pk)满足0 ≤ P0 < P1 < ... < Pk < N。

如果A[P0], A[P1], ..., A[Pk-1], A[Pk]是等差序列，则数组A的子序列切片 (P0, P1, ..., Pk) 为等差子序列切片。特别的，k ≥ 2。

函数应当返回数组A的等差子序列切片个数。

输入包含N个整数。每一个整数范围为[ -2^31, 2^31 - 1 ]，并且 0 ≤ N ≤ 1000。输出确保小于 2^31-1。

解题思路：

动态规划（Dynamic Programming）

状态转移方程：dp[x][delta] += dp[y][delta] + 1（y∈[0, x - 1]）

dp[x][delta]表示以第x个元素结尾，且公差为delta的等差子序列切片个数。

def numberOfArithmeticSlices(self, A): """ :type A: List[int] :rtype: int """ size = len(A) ans = 0 dp = [collections.defaultdict(int) for x in range(size)] for x in range(size): for y in range(x): delta = A[x] - A[y] dp[x][delta] += 1 if delta in dp[y]: dp[x][delta] += dp[y][delta] ans += dp[y][delta] return ans
https://discuss.leetcode.com/topic/67012/java-15-lines-solution
I think the idea is based on each element to cal the number of all possible differences cases. ==>
[2,4,6,8,10]
Like based on 6, to calculate the difference value of 4,2,0,-2,-4, the map is
4:1
2:2
so when we move to element 8, the map will be
6:1
4:1
2:3

    public int numberOfArithmeticSlices(int[] A) {
        int re = 0;
        HashMap<Integer, Integer>[] maps = new HashMap[A.length];
        for(int i=0; i<A.length; i++) {
            maps[i] = new HashMap<>();
            int num = A[i];
            for(int j=0; j<i; j++) {
                if((long)num-A[j]>Integer.MAX_VALUE) continue;
                if((long)num-A[j]<Integer.MIN_VALUE) continue;
                int diff = num - A[j];//\\
                int count = maps[j].getOrDefault(diff, 0);
                maps[i].put(diff, maps[i].getOrDefault(diff,0)+count+1);
                re += count;
            }
        }
        return re;
    }

http://www.itdadao.com/articles/c15a715289p0.html


X. https://leetcode.com/articles/arithmetic-slices-ii-subsequence/

We can use depth-first search to generate all subsequences. We can check a Subsequence is arithmetic or not by its definition.

Time complexity : $O(2^n)$. For each element in the array, it can be in or outside the subsequence. So the time complexity is $O(2^n)$.

  private int n;

  private int ans;

  private void dfs(int dep, int[] A, List<Long> cur) {

    if (dep == n) {

      if (cur.size() < 3) {

        return;

      }

      long diff = cur.get(1) - cur.get(0);

      for (int i = 1; i < cur.size(); i++) {

        if (cur.get(i) - cur.get(i - 1) != diff) {

          return;

        }

      }

      ans++;

      return;

    }

    dfs(dep + 1, A, cur);

    cur.add((long) A[dep]);

    dfs(dep + 1, A, cur);

    cur.remove((long) A[dep]);

  }

  public int numberOfArithmeticSlices(int[] A) {

    n = A.length;

    ans = 0;

    List<Long> cur = new ArrayList<Long>();

    dfs(0, A, cur);

    return (int) ans;

  }