Easy Java solution, no DP (3 ms)


  • 0
    A

    Here's my solution:

    Iterate through all elements up to the 3rd from the last. At each step, check the next two values. If these 3 form an Arithmetic Slice, increment the sum and remember the difference between the elements. Next, figure out how many more Slices are formed by adding on successive values.

    Keep in mind that this solution is not as efficient as some others which do it in a single pass. This is particularly true when you have very long slices (such as [1,1,1,1,1, ... ,1]).

        public int numberOfArithmeticSlices(int[] A) {
            int diff = -1;
            int sum = 0;
            if(A.length < 3) return 0;
            for(int i = 0; i < A.length - 2; i++) {
                //as long as the frontmost number fits the pattern, increment
                if(A[i+2]-A[i+1] == A[i+1]-A[i]) {
                    diff = A[i+1]-A[i];
                    sum++;
                    int j = i+2;
                    int k = i+3;
                    while(k < A.length && A[k]-A[j] == diff) {
                        sum++;
                        j++;
                        k++;
                    }
                }
            }
            return sum;
        }
    

Log in to reply
 

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