Java-The most Naive Solution 2ms


  • 0
    S

    General steps:

    1. Find out all the arithmetic(a sequence of number); let's say its length is 'count';
    2. Using the formula arithmetic slices = (count-1)*(count-2)/2, we get all the possible arithmetic slices.
    3. Add them up, we will get the final result.
    public class Solution {
        public int numberOfArithmeticSlices(int[] A) {
            if (A.length < 3) return 0;
            int diff = A[1]-A[0];
            int count = 2, res = 0;
            for (int i = 2; i < A.length; i++) {
                if (A[i]-A[i-1]==diff) {
                    count++;
                }
                else {
                    diff = A[i]-A[i-1];
                    if (count >=3) res+=(count-1)*(count-2)/2;
                    if (i<A.length-1 && A[i+1]-A[i]==diff) count = 2;
                    else if (i<A.length-1 && A[i+1]-A[i]!=diff) {
                        diff = A[i+1]-A[i];
                        count = 1;
                    }
                }
            }
            if (count >=3) res+=(count-1)*(count-2)/2;
            return res;
        }
    }
    

    Time Complexity: O(N)
    Space Complexity: O(1)
    Runtime: 2ms beats 49.59%


Log in to reply
 

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