2 3ms C++ solutions


  • 0
    H
    int numberOfArithmeticSlices_0(vector<int>& A) { // 3 ms, O(n), O(1)
    	int res = 0;
    	for (int i = 2, j = 0; i <= A.size(); i++) {
    		if (i == A.size() || A[i] - A[i - 1] != A[i - 1] - A[i - 2]) {
    			if (i - j >= 3) { // (i-1) - j + 1, sequence length
    				int n = i - j - 2; // adjusted length
    				res += (n + 1) * n / 2;
    			}
    			j = i - 1; // update starting pos to the last qualified index
    		}
    	}
    	return res;
    }
    int numberOfArithmeticSlices_1(vector<int>& A) { // 3 ms, O(n), O(1), DP
    	int cur = 0, sum = 0;
    	for (int i = 2; i < A.size(); i++) {
    		if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
    			cur += 1; // all previous sequence extends to new index, plus the last 2 with new index
    			sum += cur;
    		}
    		else {
    			cur = 0;
    		}
    	}
    	return sum;
    }

Log in to reply
 

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