Explicit Java solution (O(n) time and O(1) space)


  • 0
    M

    We can solve this by just keeping track of what the current difference is and how many consecutive elements with this difference we have already seen.

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            int n = A.length;
            if(n < 3) return 0;
            
            int counter = 0;    // counts number of all arithmetic slices
            // asume we have solution for 1...i-1.
    	// Then we can check diff = A[i]-A[i-1] and see how many previous sequences it extends
            int runningDiff = A[1] - A[0];
            int runningCount = 1;   // how many with the same runningDiff have we encountered _consecutively_
            for(int i = 2; i < n; i++) {
                int curDiff = A[i] - A[i-1];
                if(curDiff == runningDiff) {
                    runningCount++;
                    // runningCount of j implies there is an array of length j+1
                    // increasing the previous array by one element increases the number of all 3,4,5,...,j-tuples
    		// by one and introduces a new j+1 tuple.
    		// So, in total we found 3,...,(j+1) = j-1 new tuples
                    if(runningCount >= 2) counter += (runningCount - 1);
                } else {
                    runningDiff = curDiff;
                    runningCount = 1;
                }
            }
            return counter;
        }
    }
    

Log in to reply
 

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