my cpp solution with explaination


  • 0
    2

    For example, A=[1,2,3,4,5,8,9,10],
    I use a int start to store the index where the arithmetic slices begin, a int diff to store the difference between two consecutive elements. if A[i]-A[i-1]==diff, then it have max(i-start-1,0) slices.Then,add them.
    A[0]=1==>a[0]=0
    A[1]=2==>a[1]=0
    A[2]=3==>a[2]=1, [1,2,3], start=0, diff=1;
    A[3]=4==>a[3]=2, [1,2,3,4]; [2,3,4]; start=0, diff=1;
    A[4]=5==>a[4]=3, [1,2,3,4,5]; [2,3,4,5]; [3,4,5]; start=0, diff=1;
    A[5]=8==>a[5]=0; start=4, diff=3;
    A[6]=9==>a[6]=0; start=5, diff=1;
    A[7]=10==>a[7]=1; [8,9,10] ;start=5,diff=1.

    int numberOfArithmeticSlices(vector<int>& A) {
            int n=A.size();
            if(n<3) return 0;
            int sum=0;
            int i,start,diff;
            //find the first slice
            for(i=0;i<n;i++)
            {
                if(A[i+2]-A[i+1]==A[i+1]-A[i]) {
                    start=i;
                    diff=A[i+1]-A[i];
                    break;
                }
            }
            for(i=i+2;i<n;i++)
            {
                if(diff==A[i]-A[i-1])
                   sum+=max(i-start-1,0);
                else {
                    start=i-1;
                    diff=A[i]-A[i-1];
                }
            }
            return sum;
        }
    Edit1

Log in to reply
 

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