Java O(n) solution


  • 0
    D
    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            if (A == null || A.length < 3) {
                return 0;
            }
            int n = A.length;
            int[] diff = new int[n];
            for (int i = 1; i < n; i++) {
                diff[i] = A[i] - A[i - 1];
            }
            int bIndex = 1;
            int slices = 0;
            while (bIndex < n) {
                int eIndex = findEnd(diff, bIndex);
                int difflen = eIndex - bIndex + 1;
                if (difflen >= 2) {
                    slices += calcSlices(difflen + 1);
                }
                bIndex = eIndex + 1;
            }
            return slices;
        }
    
        private int findEnd(int[] diff, int index) {
            int first = diff[index];
            while (index < diff.length && diff[index] == first) {
                index++;
            }
            return index - 1;
        }
    
        private int calcSlices(int len) {
            return (len - 1) * (len - 2) / 2;
        }
    }
    

Log in to reply
 

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