413. Arithmetic Slices - cocoder39/coco39_LC GitHub Wiki

413. Arithmetic Slices

dp

Notes:

dp[i] = dp[i-1] + 1;
                res += dp[i];

O(N) time and O(N) space (space can be compressed to O(1))

public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int len = A.length;
        int dp[] = new int[len];
        int res = 0;

        for (int i = 2; i < len; i++) {
            if (A[i] - A[i-1] == A[i-1] - A[i-2]) {
                dp[i] = dp[i-1] + 1;
                res += dp[i];
            }
        }
        return res;
    }

recursion Notes: miss calling helper(A, end - 1) at invalid state is a bug O(N) time and O(N) space

class Solution {
    private int count = 0;
    public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        helper(A, A.length - 1);
        return count;
    }
    
    private int helper(int[] A, int end) {
        if (end < 2) {
            return 0;
        }
        
        boolean isValid = A[end] - A[end-1] == A[end-1] - A[end-2];
        int pre = helper(A, end - 1);
        int addOn = isValid ? pre + 1 : 0;
        count += addOn;
        
        return addOn;
    }
}

first thought: O(N^2) time DP

public int numberOfArithmeticSlices(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int len = A.length;
        boolean dp[][] = new boolean[len][len];
        int res = 0;
        
        for (int i = 1; i < len - 1; i++) {
            if (A[i] - A[i-1] == A[i+1] - A[i]) {
                dp[i-1][i+1] = true;
                res++;
            }
        }
        
        for (int l = 4; l <= len; l++) {
            for (int i = 0; i + l - 1 < len; i++) {
                int expend = i + l -1;
                dp[i][expend] = dp[i][expend-1] && A[expend] - A[expend - 1] == A[i+1] - A[i]; 
                res += dp[i][expend] ? 1 : 0;
            }
        }
        return res;
    }