java 2ms O(n) solution using DP with detail explanation


  • 4
    L

    trying to find the relationship between f(n) and f(n - 1) when A[n] can be part of current arithmetic slice.

    then easy to find that if A[n] can be the end of the current arithmetic slice, then the total number of arithmetic slices will be incremented by the length of current slice(including A[n]) - 3 + 1;

    e.g.
    when 1 2 3 --> (1, 2, 3) increment is 3 - 3 + 1 = 1
    when 1 2 3 4 --> (2, 3, 4), (1, 2, 3,4), increment is 4 - 3 + 1 = 2
    when 1 2 3 4 5 --> (3, 4, 5), (2, 3, 4, 5), (1, 2, 3, 4, 5), increment is 5 - 3 + 1 = 3.

    so the first step is to loop and store the length of arithmetic.
    second loop is to added up all the increments.

    e.g. [1 2 3 4 0 0 7 8 9]
    first loop [0 0 3 4 0 0 0 0 3];
    second loop sum = (3 - 3 + 1) + (4 - 3 + 1) + 0 + 0 + 0 + 0 + (3 - 3 + 1) = 4

    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            if(A == null || A.length == 0) return 0;
            int[] index = new int[A.length];
            for(int i = 2; i < index.length; i++)
            {
            	if(A[i] - A[i - 1] == A[i - 1] - A[i - 2])
            	{
            		if(index[i - 1] == 0) index[i] = 3;
            		else index[i] = index[i - 1] + 1;
            	}
            	else index[i] = 0;
            }
    
            int sum = 0;
            for(int i = 0; i < index.length; i++)
            {
            	if(index[i] != 0)
            	{
            		sum += index[i] - 3 + 1;
            	}
            }
            return sum;
        }
    }
    

  • 0
    V

    the example you give was incorrect,it should be:
    e.g. [1 2 3 4 0 0 7 8 9]
    first loop [0 0 3 4 0 0 0 0 3];
    second loop sum = (3 - 3 + 1) + (4 - 3 + 1) + (3 - 3 + 1) = 4


  • 0
    M
    This post is deleted!

  • 0
    L

    @vino2014zly sorry about the mistake. I correct the answer with more details. the code is correct.

    Thanks.


  • 0
    L

    @Mino-De I must mistaken the numbers, just modified it with more detail.

    and This is her. lol

    Thanks.


  • 0
    M

    @linnn_hit Ha ha. Sorry. My bad.


  • 0
    S

    I got the same as you do. Using a cache for the differences.

    public final int numberOfArithmeticSlices(final int[] a) {
            if (2 >= a.length)
                return 0;
            final int[] diff = new int[a.length - 1];
            // compute the length of differences, thus the length of diff is less 1
            for (int i = 0; i < diff.length; i++)
                diff[i] = a[i + 1] - a[i];
    
            // dp[i] = the number of arithmetic slices so far at i
            final int[] dp = new int[diff.length];
            for (int i = 1; i < dp.length; i++)
                // since it is difference, as long as 2 differences are the same
                // it is a arithmetic slices
                if(diff[i - 1] == diff[i])
                    // if the previous differences are also the same
                    // it means the length of slices now has been larger than 3
                    // give the following fact
                    // array -> the number of arithmetic slices | differences between i and (i - 1)
                    // {1}                -> 0  | nil
                    // {1, 2}             -> 0  | 0
                    // {1, 2, 3}          -> 1  | 1
                    // {1, 2, 3, 4}       -> 3  | 2
                    // {1, 2, 3, 4, 5}    -> 6  | 3
                    // {1, 2, 3, 4, 5, 6} -> 10 | 4
                    // every time, i-th element will increased by (dp[i - 1] - dp[i - 2] + 1)
                    if(1 < i && diff[i - 2] == diff[i - 1]) 
                        // dp[i] = dp[i - 1] + (dp[i - 1] - dp[i - 2] + 1);
                        dp[i] = 2 * dp[i - 1] - dp[i - 2] + 1;
                    else
                        dp[i] = dp[i - 1] + 1;
                else
                    dp[i] = dp[i - 1];
    
            return dp[diff.length - 1];
        }
    

Log in to reply
 

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