[N-0] add 724

fishercoder1534 · fishercoder1534 · commit c43bd39f94db · 2017-11-12T08:47:50.000-05:00
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
+|724|[Find Pivot Index](https://leetcode.com/problems/find-pivot-index/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_724.java) | O(n) | O(n) | Easy | Array
 |723|[Candy Crush](https://leetcode.com/problems/candy-crush/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_723.java) | O((r*c)^2) | O((r*c)) | Medium | Array, Two Pointers
 |721|[Accounts Merge](https://leetcode.com/problems/accounts-merge/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_721.java) |  | | Medium | DFS, Union Find
 |720|[Longest Word in Dictionary](https://leetcode.com/problems/longest-word-in-dictionary/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_720.java) | O(∑wi) where wi is the length of words[i] | O(∑wi) where wi is the length of words[i] | Easy | Trie
diff --git a/src/main/java/com/fishercoder/solutions/_724.java b/src/main/java/com/fishercoder/solutions/_724.java
@@ -0,0 +1,51 @@
+package com.fishercoder.solutions;
+
+/**
+ * 724. Find Pivot Index
+ *
+ * Given an array of integers nums, write a method that returns the "pivot" index of this array.
+ * We define the pivot index as the index where the sum of the numbers to the left of the index is equal
+ * to the sum of the numbers to the right of the index.
+ * If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.
+
+ Example 1:
+ Input:
+ nums = [1, 7, 3, 6, 5, 6]
+ Output: 3
+ Explanation:
+ The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
+ Also, 3 is the first index where this occurs.
+
+ Example 2:
+ Input:
+ nums = [1, 2, 3]
+ Output: -1
+ Explanation:
+ There is no index that satisfies the conditions in the problem statement.
+
+ Note:
+ The length of nums will be in the range [0, 10000].
+ Each element nums[i] will be an integer in the range [-1000, 1000].
+ */
+public class _724 {
+    public static class Solution1 {
+        public int pivotIndex(int[] nums) {
+            if (nums == null || nums.length == 0) {
+                return -1;
+            }
+            int[] sums = new int[nums.length];
+            sums[0] = nums[0];
+            for (int i = 1; i < nums.length; i++) {
+                sums[i] = sums[i - 1] + nums[i];
+            }
+            int result = -1;
+            for (int i = 0; i < nums.length; i++) {
+                if (i == 0 && 0 == sums[nums.length - 1] - sums[i] || (i > 0 && sums[i - 1] == sums[nums.length - 1] - sums[i])) {
+                    result = i;
+                    break;
+                }
+            }
+            return result;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_724Test.java b/src/test/java/com/fishercoder/_724Test.java
@@ -0,0 +1,42 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._724;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _724Test {
+    private static _724.Solution1 solution1;
+    private static int[] nums;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _724.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        nums = new int[]{1, 7, 3, 6, 5, 6};
+        assertEquals(3, solution1.pivotIndex(nums));
+    }
+
+    @Test
+    public void test2() {
+        nums = new int[]{1, 2, 3};
+        assertEquals(-1, solution1.pivotIndex(nums));
+    }
+
+    @Test
+    public void test3() {
+        nums = new int[]{-1, -1, -1, 0, 1, 1};
+        assertEquals(0, solution1.pivotIndex(nums));
+    }
+
+    @Test
+    public void test4() {
+        nums = new int[]{-1, -1, 0, 1, 1, 0};
+        assertEquals(5, solution1.pivotIndex(nums));
+    }
+
+}
