add 446

fishercoder1534 · fishercoder1534 · commit 9330f0d7a142 · 2017-07-29T09:05:28.000-07:00
diff --git a/README.md b/README.md
@@ -170,6 +170,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |449|[Serialize and Deserialize BST](https://leetcode.com/problems/serialize-and-deserialize-bst/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_449.java)| O(n)|O(h) | Medium| BFS
 |448|[Find All Numbers Disappeared in an Array](https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_448.java)| O(n)|O(1) | Easy| Array, HashMap
 |447|[Number of Boomerangs](https://leetcode.com/problems/number-of-boomerangs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_447.java)| O(n^2)|O(n) | Easy| HashMap
+|446|[Arithmetic Slices II - Subsequence](https://leetcode.com/problems/arithmetic-slices-ii-subsequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_446.java)| O(n^2)|O(n^2) | Hard| DP
 |445|[Add Two Numbers II](https://leetcode.com/problems/add-two-numbers-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_445.java)| O(max(m,n)|O(max(m,n)) | Medium| Stack, LinkedList
 |444|[Sequence Reconstruction](https://leetcode.com/problems/sequence-reconstruction/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_444.java)| O(n)|O(n) | Medium| Topological Sort, Graph
 |442|[Find All Duplicates in an Array](https://leetcode.com/problems/find-all-duplicates-in-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_442.java)| O(n)|O(1) | Medium| Array
diff --git a/src/main/java/com/fishercoder/solutions/_446.java b/src/main/java/com/fishercoder/solutions/_446.java
@@ -0,0 +1,69 @@
+package com.fishercoder.solutions;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * 446. Arithmetic Slices II - Subsequence
+ *
+ * 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.
+
+ For example, these are arithmetic sequences:
+
+ 1, 3, 5, 7, 9
+ 7, 7, 7, 7
+ 3, -1, -5, -9
+
+ The following sequence is not arithmetic.
+
+ 1, 1, 2, 5, 7
+
+ 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.
+
+ 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.
+
+ The function should return the number of arithmetic subsequence slices in the array A.
+
+ 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.
+
+
+ Example:
+
+ Input: [2, 4, 6, 8, 10]
+
+ Output: 7
+
+ Explanation:
+ All arithmetic subsequence slices are:
+ [2,4,6]
+ [4,6,8]
+ [6,8,10]
+ [2,4,6,8]
+ [4,6,8,10]
+ [2,4,6,8,10]
+ [2,6,10]
+ */
+public class _446 {
+    /**reference: https://discuss.leetcode.com/topic/67413/detailed-explanation-for-java-o-n-2-solution*/
+    public int numberOfArithmeticSlices(int[] A) {
+        int res = 0;
+        Map<Integer, Integer>[] map = new Map[A.length];
+
+        for (int i = 0; i < A.length; i++) {
+            map[i] = new HashMap<>(i);
+
+            for (int j = 0; j < i; j++) {
+                long diff = (long) A[i] - A[j];
+                if (diff <= Integer.MIN_VALUE || diff > Integer.MAX_VALUE) continue;
+
+                int d = (int) diff;
+                int c1 = map[i].getOrDefault(d, 0);
+                int c2 = map[j].getOrDefault(d, 0);
+                res += c2;
+                map[i].put(d, c1 + c2 + 1);
+            }
+        }
+
+        return res;
+    }
+}
