446. Arithmetic Slices II - Subsequence

446. 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]

----------------------------
递归，超时

class Solution {
    
    public int numberOfArithmeticSlices(int[] A) {
        
        return dfs(A, 0, new ArrayList<Integer>());
    }
    
    private int dfs(int[] A, int i, List<Integer> cur) {
        int count = 0;
        if (cur.size() > 2) {
            if ((long)cur.get(cur.size() - 1) - (long)cur.get(cur.size() - 2) ==
                    (long)cur.get(cur.size() - 2) - (long)cur.get(cur.size() - 3)) {
                count++;
            }else {
                return 0;
            }
        }
        
        for (; i < A.length; i++) {
            List<Integer> t = new ArrayList<>(cur);
            t.add(A[i]);
            count += dfs(A, i + 1, t);
        }
        
        return count;
    }
}

Solution #2, memoization。 OA超时，都是超时的个例在test run可以过

class Solution {
    
    public int numberOfArithmeticSlices(int[] A) {
        
        return dfs(A, 0, new ArrayList<Integer>(), new HashMap<String, Integer>());
    }
    
    private int dfs(int[] A, int i, List<Integer> cur, Map<String, Integer> dp) {
        int count = 0;
        int n = cur.size();
        if (n > 2) {
            if ((long)cur.get(n - 1) - (long)cur.get(n - 2) == (long)cur.get(n - 2) - (long)cur.get(n - 3)) count++;
        }
        
        for (; i < A.length; i++) {
            if (n > 1) {
                if ((long)cur.get(n - 1) - (long)cur.get(n - 2) == (long)A[i] - (long)cur.get(n - 1)) {
                    int diff = A[i] - cur.get(n - 1);
                    String key = diff + "" + i;
                    
                    if (dp.containsKey(key)) {
                        count += dp.get(key);
                    }else {
                        List<Integer> t = new ArrayList<>(cur);
                        t.add(A[i]);
                        int tmp = dfs(A, i + 1, t, dp);
                        dp.put(key, tmp);
                        count += tmp;    
                    }
                }
            }else {
                List<Integer> t = new ArrayList<>(cur);
                t.add(A[i]);
                count += dfs(A, i + 1, t, dp);
            }
            
        }
        
        return count;
    }
}

dp[i]存的是以A[i]为末尾的subsequence的所有满足条件的diff的长度。
算法的思路是拿A[i]依次与[0, i]凑
ref: https://leetcode.com/problems/arithmetic-slices-ii-subsequence/discuss/92822/Detailed-explanation-for-Java-O(n2)-solution

Followup, 如果修改长度为4怎么做？
额外设计数据机构，对每一个i要记录长度和count, 而且对不同长度的count要分开计算

class Solution {
    
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        Map<Integer, Integer>[] dp = new Map[n];
        int rt = 0;
        
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<Integer, Integer>();
            
            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 di = (int) diff;
                int c1 = dp[i].getOrDefault(di, 0);
                int c2 = dp[j].getOrDefault(di, 0);
                rt += c2;
                dp[i].put(di, c1 + c2 + 1);
            }
        }
        
        return rt;
    }
}

Partial的follow up，不一定对，暂时先放在这里

class Solution {
    class Cus{
        public int length;
        public int count;
        public Cus() {
            length = 1;
            count = 0;
        }
    }
    
    public int numberOfArithmeticSlices(int[] A) {
        int n = A.length;
        Map<Integer, Cus>[] dp = new Map[n];
        int rt = 0;
        
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<Integer, Integer>();
            
            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 di = (int) diff;
                Cus c1 = null;
                if (dp[i].containsKey(di)) {
                    c1 = dp[i].get(di);
                }else {
                    c1 = new Pair();
                }
                
                Cus c2 = null;
                if (dp[j].containsKey(di)) {
                    c2 = dp[j].get(di);
                }else {
                    c2 = new Pair();
                }
                
                c2.length++;
                if (c2.length > 2) {
                    rt += c2.count;
                }
                
                c1.length = c2
                
                int c1 = dp[i].getOrDefault(di, 0);
                int c2 = dp[j].getOrDefault(di, 0);
                rt += c2;
                dp[i].put(di, c1 + c2 + 1);
            }
        }
        
        return rt;
    }
}