|
| 1 | +packagecom.fishercoder.solutions; |
| 2 | + |
| 3 | +importjava.util.HashMap; |
| 4 | +importjava.util.Map; |
| 5 | + |
| 6 | +/** |
| 7 | + * 446. Arithmetic Slices II - Subsequence |
| 8 | + * |
| 9 | + * A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. |
| 10 | +
|
| 11 | + For example, these are arithmetic sequences: |
| 12 | +
|
| 13 | + 1, 3, 5, 7, 9 |
| 14 | + 7, 7, 7, 7 |
| 15 | + 3, -1, -5, -9 |
| 16 | +
|
| 17 | + The following sequence is not arithmetic. |
| 18 | +
|
| 19 | + 1, 1, 2, 5, 7 |
| 20 | +
|
| 21 | + A zero-indexed array A consisting of N numbers is given. A subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk < N. |
| 22 | +
|
| 23 | + A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2. |
| 24 | +
|
| 25 | + The function should return the number of arithmetic subsequence slices in the array A. |
| 26 | +
|
| 27 | + The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1. |
| 28 | +
|
| 29 | +
|
| 30 | + Example: |
| 31 | +
|
| 32 | + Input: [2, 4, 6, 8, 10] |
| 33 | +
|
| 34 | + Output: 7 |
| 35 | +
|
| 36 | + Explanation: |
| 37 | + All arithmetic subsequence slices are: |
| 38 | + [2,4,6] |
| 39 | + [4,6,8] |
| 40 | + [6,8,10] |
| 41 | + [2,4,6,8] |
| 42 | + [4,6,8,10] |
| 43 | + [2,4,6,8,10] |
| 44 | + [2,6,10] |
| 45 | + */ |
| 46 | +publicclass_446 { |
| 47 | +/**reference: https://discuss.leetcode.com/topic/67413/detailed-explanation-for-java-o-n-2-solution*/ |
| 48 | +publicintnumberOfArithmeticSlices(int[]A) { |
| 49 | +intres =0; |
| 50 | +Map<Integer,Integer>[]map =newMap[A.length]; |
| 51 | + |
| 52 | +for (inti =0;i <A.length;i++) { |
| 53 | +map[i] =newHashMap<>(i); |
| 54 | + |
| 55 | +for (intj =0;j <i;j++) { |
| 56 | +longdiff = (long)A[i] -A[j]; |
| 57 | +if (diff <=Integer.MIN_VALUE ||diff >Integer.MAX_VALUE)continue; |
| 58 | + |
| 59 | +intd = (int)diff; |
| 60 | +intc1 =map[i].getOrDefault(d,0); |
| 61 | +intc2 =map[j].getOrDefault(d,0); |
| 62 | +res +=c2; |
| 63 | +map[i].put(d,c1 +c2 +1); |
| 64 | + } |
| 65 | + } |
| 66 | + |
| 67 | +returnres; |
| 68 | + } |
| 69 | +} |