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

• 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;
}

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

• @bhimaraju Yes, that's correct

• 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.

• 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);
}

if (index != A.Length) {
start = index - 1;
diff = A[index] - A[index-1];
}
}

index++;
}

return result;
}
}

• still have space to improve

• @shiyanch Nice solution. I think this is the straightforward solution that us mere mortals can strive for.

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