C# Solution, O(n) Time, O(1) space


  • 0
    S
    public int NumberOfArithmeticSlices(int[] A) {
            if (A.Length < 3) return 0;
    			int first = 0;
    			int last = 2;
    			int slices = 0;
    			return GetArithmeticSlices(A, first, last, slices);
        }
        
        private int GetArithmeticSlices(int[] A, int first, int last, int slices)
    		{
    			if (first < 0 || first >= A.Length || last < 0 || last >= A.Length) return slices;
    			var diff = 0;
    			if (IsArithmetic(A, first, last))
    			{
    				slices++;
    				diff = A[last] - A[last - 1];
    				last++;
    			}
    			else
    			{
    				return GetArithmeticSlices(A, first+1, last+1, slices);
    			}
    
    			while (last < A.Length)
    			{
    				if (A[last] - A[last - 1] == diff)
    				{
                        slices++;
    					var indexDiff = last - first + 1;
    					slices += ((indexDiff/3)-1)*3;
    					slices += (indexDiff%3);
    					last++;
    				}
    				else
    				{
    					return GetArithmeticSlices(A, last, last + 2, slices);
    				}
    			}
    
    			return slices;
    		}
    
    		private bool IsArithmetic(int[] A, int first, int last)
    		{
    			if (A == null || A.Length < 3 || first < 0 || first >= A.Length || last < 0 || last >= A.Length || first >= last) return false;
    
    			var diff = A[first + 1] - A[first];
    
    			for (int i = first + 1; i < last; i++)
    			{
    				if (A[i + 1] - A[i] != diff) return false;
    			}
    
    			return true;
    		}
    
    

Log in to reply
 

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