[leetcode] arithmetic slices

problem

code

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        // sliding door
        // P P+1 P+2 is arithmetic, count = 1, sum = 1
        // try P+1 P+2 P+3 count = 2, sum = 1 + 2
        // if no, count = 0, sum = 1 + 2;
        // start P+2 P+3 P+4 until Q
        
        
        int[] dp = new int[A.length]; // to store count
        int sum = 0;
        for (int i = 2; i < A.length; i++)
        {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2])
            {
                dp[i] = 1 + dp[i - 1];
                sum += dp[i];
            }
        }
        return sum;
        
    }

Time: O(N)
Space: O(N), how to make this to O(1)?

• O(1) space

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
		int count = 0;
		int sum = 0;
        for (int i = 2; i < A.length; i++)
        {
            if (A[i] - A[i - 1] == A[i - 1] - A[i - 2])
            {
                count++;
                sum += count;
            }
            else
            {
            	count = 0;
            }
        }
        return sum;
    }

recursion solution from leetcode

public class Solution {
    int sum = 0;
    public int numberOfArithmeticSlices(int[] A) {
        slices(A, A.length - 1);
        return sum;
    }
    
    // 1 2 3 4 5 6 7, ap = 1+1+1+1+1+1+0 sum += 6
    // 7 - 6 == 6 - 5 ...
    // 6 - 5 == 5 - 4 ..
    //  5 - 4 == 4 - 3, ap = 1+1+1+0 sum += 3
    // 4- 3 == 3 - 2, ap = 1+1+0, sum += 2 
    // 2 - 1 == 1 - 0, ap = 1 + 0, su += 1
    // 1 return 0
    public int slices(int[] A, int i) {
        if (i < 2)
            return 0;
        int ap = 0;
        if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
            ap = 1 + slices(A, i - 1);
            sum += ap;
        } else
            slices(A, i - 1);
        return ap;
    }
}