2 Different AC JAVA Solution, Using Two Pointer and DP


  • 0

    DP is my first idea for this problem, it is based on the rules:

    if we want to find out whether [a,b,c,d] is arithmetic, we just need to find out the result of ([a,b,c] is arithmetic) && (d-c == c-b), Here comes to DP Solution:

    public int numberOfArithmeticSlices(int[] A) {
        int count = 0;
        boolean[][] dp = new boolean[A.length][A.length];
        for (int i = 0; i < A.length-2; i++) {
            if ((A[i+2]-A[i+1]) == (A[i+1]-A[i])) { 
                dp[i][i+2] = true;
                count++;
            }
        }
        for (int k = 3; k < A.length; k++){
            for (int i = 0; i < A.length-k; i++){
                dp[i][i+k] = (dp[i][i+k-1] && (A[i+k]-A[i+k-1] == A[i+1]-A[i]));
                if (dp[i][i+k]) count++;
            }
        }
        return count;
    }
    

    Although DP can get the right answers, it is too slow, O(n2).

    The second idea is to search from the largest arithmetic slices, if [a,b,c,d,e] is arithmetic, all its subset (length >= 3) must be arithmetic. the total number of the arithmetic subsets will be (5-1)(5-2)/2. To achieve that, we just use two pointers to monitor the start and the end of the arthmetic slices, Here comes the code:

    public int numberOfArithmeticSlices(int[] A) {
        int count = 0;
        int tempLength = 0, i = 0, ptr = 2;
        while (i < A.length-2){
            if (ptr < A.length && (A[i+1]-A[i]) == (A[ptr]-A[ptr-1]))
                ptr++;
            else{
                tempLength = ptr-i;
                if (tempLength != 2 || (A[i+2] - A[i+1]) == (A[i+1]-A[i]))
                    count += ((tempLength-1)*(tempLength-2) / 2);
                int temp = i;
                i = ptr-1; ptr = i+2;
            }
        }
        return count;
    }

Log in to reply
 

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