arithmetic slices

fishercoder1534 · fishercoder1534 · commit 9076ca2ac0dc · 2016-11-06T09:30:53.000-08:00
diff --git a/MEDIUM/src/medium/ArithmeticSlices.java b/MEDIUM/src/medium/ArithmeticSlices.java
@@ -0,0 +1,40 @@
+package medium;
+
+public class ArithmeticSlices {
+
+    //copied this solution: https://discuss.leetcode.com/topic/62884/2ms-java-o-n-time-o-1-space-solution
+    public int numberOfArithmeticSlices(int[] A) {
+        int sum = 0, len = 2;
+        for (int i = 2; i < A.length; i++){
+            if (A[i] - A[i-1] == A[i-1] - A[i-2]){
+                len++;
+            } else {
+                if (len > 2) sum += calculateSlices(len);
+                len = 2;//reset it to 2
+            }
+        }
+        if(len > 2) sum += calculateSlices(len);
+        return sum;
+    }
+    
+    int calculateSlices(int len){
+        return (len-1)*(len-2)/2;
+    }
+    
+    class Solution2{
+        //a more clear solution: https://discuss.leetcode.com/topic/63302/simple-java-solution-9-lines-2ms
+        public int numberOfArithmeticSlices(int[] A) {
+            int sum = 0, curr = 0;
+            for (int i = 2; i < A.length; i++){
+                if (A[i] - A[i-1] == A[i-1] - A[i-2]){
+                    curr++;
+                    sum += curr;
+                } else {
+                    curr = 0;
+                }
+            }
+            return sum;
+        }
+    }
+
+}
diff --git a/README.md b/README.md
@@ -6,6 +6,7 @@
 |419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../../blob/master/MEDIUM/src/medium/BattleshipsinaBoard.java) | O(n^2) |O(1) | Medium| DFS
 |417|[Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)|[Solution](../../blob/master/MEDIUM/src/medium/PacificAtlanticWaterFlow.java) | O(m*n*Max(m,n)) |O(m*n) | Medium| DFS
 |415|[Add Strings](https://leetcode.com/problems/add-strings/)|[Solution](../../blob/master/EASY/src/easy/AddStrings.java)| O(n)|O(1) | Easy|
+|413|[Arithmetic Slices](https://leetcode.com/problems/arithmetic-slices/)|[Solution](../../blob/master/MEDIUM/src/medium/ArithmeticSlices.java) | O(n) |O(1) | Medium| DP
 |412|[Fizz Buzz](https://leetcode.com/problems/fizz-buzz/)|[Solution](../../blob/master/EASY/src/easy/FizzBuzz.java)| O(n)|O(1) | Easy|
 |404|[Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/)|[Solution](../../blob/master/EASY/src/easy/SumofLeftLeaves.java)| O(n)|O(h) | Easy|
 |398|[Random Pick Index](https://leetcode.com/problems/random-pick-index/)|[Solution](../../blob/master/MEDIUM/src/medium/RandomPickIndex.java) | | | Medium| Reservoir Sampling
