2ms Java non-dp solution


  • 0
    S

    The idea is to find every subarray (as long as possible) that is a valid arithmetic sequence from s to e. Then add up the number of chunks that each subarray can contribute.

    public int numberOfArithmeticSlices(int[] A) {
        if (A.length < 3) return 0;
        
        int result = 0;
        
        int s = 0;
        int e = 1;
        int d = A[s+1] - A[s]; 
        for (; e < A.length; e ++) {
            if (e == A.length-1) {
                result += numOfChunks(s, e);
                break;
            }
            if (A[e]+d != A[e+1]) {
                result += numOfChunks(s, e);
                s = e;
                d = A[e+1] - A[s];
            }
        }
        
        return result;
    }
    
    private int numOfChunks(int s, int e) {
        int n = e-s+1;
        if (n < 3) return 0;
        
        return ((n-1)*(n-2))/2;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.