4Sum II

fishercoder1534 · fishercoder1534 · commit 2488960d562c · 2016-11-22T16:41:13.000-08:00
diff --git a/MEDIUM/src/medium/_4SumII.java b/MEDIUM/src/medium/_4SumII.java
@@ -0,0 +1,43 @@
+package medium;
+
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.Map;
+
+public class _4SumII {
+
+    /**Although it's tagged with BinarySearch and HashTable, I didn't come up with a good BinarySearch solution, then looked at this post:
+     * https://discuss.leetcode.com/topic/67658/simple-java-solution-with-explanation*/
+    public static int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
+        Map<Integer, Integer> map = new HashMap();
+        int result = 0, len = A.length;
+        for (int i = 0; i < len; i++){
+            for (int j = 0; j < len; j++){
+                int sum = A[i] + B[j];
+                if (map.containsKey(sum)){
+                    map.put(sum, map.get(sum)+1);
+                } else {
+                   map.put(sum, 1); 
+                }
+            }
+        }
+        
+        for (int i = 0; i < len; i++){
+            for (int j = 0; j < len; j++){
+                int sum = -(C[i] + D[j]);
+                if(map.containsKey(sum)) result += map.get(sum);
+            }
+        }
+        
+        return result;
+    }
+
+    public static void main(String...args){
+        int[] A = new int[]{1,2};
+        int[] B = new int[]{-2,-1};
+        int[] C = new int[]{-1,2};
+        int[] D = new int[]{0,2};
+        
+        System.out.println(fourSumCount(A, B, C, D));
+    }
+}
diff --git a/README.md b/README.md
@@ -6,6 +6,7 @@
 |459|[Repeated Substring Pattern](https://leetcode.com/problems/repeated-substring-pattern/)|[Solution](../../blob/master/EASY/src/easy/RepeatedSubstringPattern.java)| O(n)|O(n) | Easy| KMP
 |456|[132 Pattern](https://leetcode.com/problems/132-pattern/)|[Solution](../../blob/master/MEDIUM/src/medium/_132Pattern.java) | O(n) |O(n) | Medium| Stack
 |455|[Assign Cookies](https://leetcode.com/problems/assign-cookies/)|[Solution](../../blob/master/EASY/src/easy/AssignCookies.java)| O(n)|O(1) | Easy|
+|454|[4Sum II](https://leetcode.com/problems/4sum-ii/)|[Solution](../../blob/master/MEDIUM/src/medium/_4SumII.java) | O(n) |O(n) | Medium| HashMap
 |453|[Minimum Moves to Equal Array Elements](https://leetcode.com/problems/minimum-moves-to-equal-array-elements/)|[Solution](../../blob/master/EASY/src/easy/MinimumMovestoEqualArrayElements.java)| O(n)|O(1) | Easy|
 |447|[Number of Boomerangs](https://leetcode.com/problems/number-of-boomerangs/)|[Solution](../../blob/master/EASY/src/easy/NumberofBoomerangs.java)| O(n^2)|O(n) | Easy| HashMap
 |441|[Arranging Coins](https://leetcode.com/problems/arrange-coins/)|[Solution](../../blob/master/EASY/src/easy/ArrangingCoins.java)| O(n)|O(1) | Easy|
