simple Java solution using DP


  • 1
    F
    public int numberOfArithmeticSlices(int[] A) {
            int len=A.length;
            if(len<3) return 0;
            int[] dp=new int[len];
            int res=0;
            for(int i=2;i<len;i++)
            {
                if(A[i]-A[i-1]==A[i-1]-A[i-2])
                    dp[i]=dp[i-1]+1;
                else
                    dp[i]=0;
                res+=dp[i];
            }
            return res;
        }
    

    The basic idea is that the array dp record the number of arithmetic sequences end at A[i]. If A[i],A[i-1],A[i-2] is an arithmetic sequence, we get one more ending at A[i] than A[i-1]; If they are not, we assign 0 to dp[i] because we need to start over. When we traverse the array, we just add all the values up to get the result.


Log in to reply
 

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