2ms Java O(n) time, O(1) space solution


  • 11
    S
    public int numberOfArithmeticSlices(int[] A) {
            if(A == null || A.length < 3)
                return 0;
            int sum = 0;
            int len = 2;
    
            for(int i=2;i<A.length;i++) {
    
                // keep increasing the splice
                if(A[i] - A[i-1] == A[i-1] - A[i-2]) {
                    len++;
                }
                else {
                    if(len > 2) {
                        sum += calculateSlices(len);
                    }
                    // reset the length of new slice
                    len = 2;
                }
            }
            // add up the slice in the rear
            if(len>2)
                sum += calculateSlices(len);
    
            return sum;
        }
    
        private int calculateSlices(int n){
            return (n-1)*(n-2)/2;
        }
    

  • 0
    B

    Does the function calculateSlices represent the total number of ways we can pick 3 elements from n elements nC3?


  • 0
    S

    @bhimaraju Yes, that's correct


  • 2
    B

    Hmmm, to me it looks more like the sum of the first n-2 numbers...

    For example, if your sequence was 2,4,6,8,10, then you have the following sub sequences formed:

    1. 2,4,6, 4,6,8, 6,8,10: 3 sub sequences, or rather 5-2 sequences
    2. 2,4,6,8, 4,6,8,10: 2 sub sequences
    3. 2,4,6,8,10: 1 sub sequence

    Thus the total number of sequences is 3+2+1 or in other words, the sum from 1..n-2, which is (n-1)*(n-2)/2.


  • 0

    Here's a C# solution to merge the if (len>2) condition inside the loop.

    public class Solution {
        public int NumberOfArithmeticSlices(int[] A) {
            if (A == null || A.Length < 3) {
                return 0;
            }
            
            // Init the state
            int start = 0;
            int index = 2;
            int diff = A[1] - A[0];
            int result = 0;
            
            while(index <= A.Length) {
                // when reach to end or detect the end of arithmetic
                if (index == A.Length || A[index] - A[index-1] != diff) {
                    // calculate the result. When the sequence number is n,
                    // the result is 1 + 2 + 3 + ... + n - 2
                    // i.e., n*(n+1)/2 - n - (n-1)
                    if (index - start >= 3) {
                        int n = index - start;
                        result += n * (n + 1) / 2 - n - (n-1);
                    }
                    
                    // start with the new potential arithmetic
                    if (index != A.Length) {
                        start = index - 1;
                        diff = A[index] - A[index-1];
                    }
                }
                
                index++;
            }
            
            return result;
        }
    }
    

  • 0
    R

    still have space to improve


Log in to reply
 

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