public int numberOfArithmeticSlices(int[] A) {
int curr = 0, sum = 0;
for (int i=2; i<A.length; i++)
if (A[i]A[i1] == A[i1]A[i2]) {
curr += 1;
sum += curr;
} else {
curr = 0;
}
return sum;
}
Simple Java solution 9 lines, 2ms

@lcl7722 Clever! thanks for the concise code.
If I understand correctly, the way it works is:
i) We need minimum 3 indices to make arithmetic progression,
ii) So start at index 2, see if we got two diffs same, so we get a current 1 arith sequence
iii) At any index i, if we see it forms arith seq with former two, that means running (curr) sequence gets extended upto this index, at the same time we get one more sequence (the three numbers ending at i), so curr++. Any time this happens, add the curr value to total sum.
iv) Any time we find ith index does not form arith seq, make currently running no of seqs to zero.

sum += curr
really does the trick. Brilliant!I think the easy way to understand this is that adding current number to our existing arithmetic sequence, we will have
curr
additional combinations of new arithmetic slices.Let's say if we have
[1, 2, 3, 4]
and currently we have3
arithmetic slices (curr
is2
). We are going to add5
to our arithmetic sequence. So that we will havecurr
new slices (curr
is3
), which is[3, 4, 5], [2, 3, 4, 5] and [1, 2, 3, 4, 5]
. Now, the total valid arithmetic slices is3 + curr = 6
. That's exactly the same assum += curr
.

if (A[i]A[i1] == A[i1]A[i2])
this introduces an integer overflow bug.If the input is [Integer.MIN_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE  1], it returns 1, but it should be 0.
Correction:
public int numberOfArithmeticSlices(int[] A) { int curr = 0, sum = 0; for (int i = 2; i < A.length; i++) { if ((long)A[i]  A[i  1] == (long)A[i  1]  A[i  2]) { curr += 1; sum += curr; } else curr = 0; } return sum; }



Nice solution, very concise. The way I think about it is as your slice grows by 1, you have created the 1 longer slice plus a new position for each of the lengths you have already created. So, if you have a slice that is length 5 you will have slices of lengths 5, 4, 3 (all but the largest have multiple positions). If you now grow from 5 to 6, you create a new slice of length 6 and a new position for 5, 4, and 3.
Here's the DP part, but really you only need to hang onto the previous result or apply the logic directly in the code.
f(length of sequece) = number of slices you can make f(len) = 1 + f(len  1) + (len  3) f(2) = 0 f(3) = 1 + f(2) + (3  3) = 1 f(4) = 1 + f(3) + (4  3) = 3 f(5) = 1 + f(4) + (5  3) = 6 f(6) = 1 + f(5) + (6  3) = 10 f(7) = 1 + f(6) + (7  3) = 15 f(8) = 1 + f(7) + (8  3) = 21 f(9) = 1 + f(8) + (9  3) = 28
public int NumberOfArithmeticSlices(int[] A) { int count = 0; for (int start = 0; start < A.Length  2; start++) { int delta = A[start+1]  A[start]; // for this starting point discover the length // NOTE: this is additional length from 3 onwards (3 will have a "len = 1") int len = 0; for (int i = start + 2; i < A.Length; i++) { if (A[i]  A[i1] == delta) { len++; count += len; // 1 for each length } else { break; } } // skip to final element in the sequence for next start position start += len; } return count; }

said in Simple Java solution 9 lines, 2ms:
sum += curr
Very concise solution! But it seems to update the total count by
sum += curr
every time if the common difference is same. It could updatesum
only when common difference changes by a total of(subsum1)*(subsum2)/2
.

@Free9
thank you for explain it, i wander why not count [1,3,5] ,if[1,2,3,4,5] is Arithmetic Slices ,then [1,3,5] must also be Arithmetic Slices.can you explain it?

@guk said in Simple Java solution 9 lines, 2ms:
@Free9
thank you for explain it, i wander why not count [1,3,5] ,if[1,2,3,4,5] is Arithmetic Slices ,then [1,3,5] must also be Arithmetic Slices.can you explain it?Note that in this problem, the slice is defined as subsequence with consecutive index, so [1,3,5] does not qualify for arithmetic slices.
The example you are making is actually for the harder version 446. arithmetic slices II.

@rohan5 said in Simple Java solution 9 lines, 2ms:
These are just slices of length 3, what about slices of length 4, 5, ... A.Length3 ?
Won't they increase the overall slice count ?Actually, it already counted all slices with length at least 3 (which is the definition). Line
curr += 1
counts the number of arithmetic slices ending with current number andsum += curr
just adds up the counts towards the total.

I can see it now,
we are basically assuming an extra slice, ie, if
1 2 3 is a slice and 2 3 4 is a slice then 1 2 3 4 must be a slice.
Thus, we do curr+=1 and not cur = 1.We've basically assumed 1 2 3 4 is a slice and when we reach 2 3 4 we have 2 slices to add to the current sum.
If we had nums uptil 5 and we reached 3 4 5, we would have 3 slices to add to current sum.

@rohan5 Yes, that is the basic idea for the key line
sum += curr
.Actually, I prefer to scan all the way to the end of a longest arithmetic subsequence before start counting the
sum
(which I personally think more readable in logic) simply because of the following fact: Arithmetic array of size
N
has exactly(N1)*(N2)/2
arithmetic slices (length >= 3).
Also, it will minimize the number of times to update
sum
. I had a post here if you are interested.
 Arithmetic array of size


@rohan5 said in Simple Java solution 9 lines, 2ms:
@zzg_zzm Where did you get that formula (N1)*(N2)/2 ?
Just count total number of arithmetic slices by various lengths. For any given arithmetic array
A
of sizeN
, it has1
arithmetic slice of lengthN
(itself);2
arithmetic slices of lengthN1
(0~N2 and 1~N1);3
arithmetic slices of lengthN2
;
...N2
arithmetic slices of length3
.
So the total count of arithmetic slices is
1+2+3+...+(N2) = (N1)*(N2)/2
.Or simply using combination number C_{N}^{2}  (N1) = (N1)*(N2)/2 (taking any 2 indices from N indices but they cannot be adjacent).