refactor 167

fishercoder1534 · fishercoder1534 · commit 0460edc705cf · 2021-09-14T15:54:37.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_167.java b/src/main/java/com/fishercoder/solutions/_167.java
@@ -1,27 +1,13 @@
 package com.fishercoder.solutions;
 
-/**
- * 167. Two Sum II - Input array is sorted
-
- Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
-
- The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
-
- Note:
-
- Your returned answers (both index1 and index2) are not zero-based.
- You may assume that each input would have exactly one solution and you may not use the same element twice.
-
- Example:
-
- Input: numbers = [2,7,11,15], target = 9
- Output: [1,2]
- Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
-
- */
+import java.util.Arrays;
 
 public class _167 {
     public static class Solution1 {
+        /**
+         * This is an amazing solution!
+         * Time: O(logn)
+         */
         public int[] twoSum(int[] numbers, int target) {
             int left = 0;
             int right = numbers.length - 1;
@@ -38,4 +24,56 @@ public int[] twoSum(int[] numbers, int target) {
             return new int[]{-1, -1};
         }
     }
+
+    public static class Solution2 {
+        /**
+         * Time: O(nlogn)
+         */
+        public int[] twoSum(int[] numbers, int target) {
+            for (int i = 0; i < numbers.length - 1; i++) {
+                int index = exists(Arrays.copyOfRange(numbers, i + 1, numbers.length), target - numbers[i]);
+                if (index >= 0) {
+                    return new int[]{i + 1, index + 2 + i};
+                }
+            }
+            return null;
+        }
+
+        private int exists(int[] nums, int target) {
+            int left = 0;
+            int right = nums.length - 1;
+            while (left < right) {
+                int mid = left + (right - left) / 2;
+                if (nums[mid] == target) {
+                    return mid;
+                } else if (nums[mid] < target) {
+                    left = mid + 1;
+                } else {
+                    right = mid - 1;
+                }
+            }
+            return nums[left] == target ? left : (right >= 0 && nums[right] == target) ? right : -1;
+        }
+    }
+
+    public static class Solution3 {
+        /**
+         * Time: O(nlogn)
+         */
+        public int[] twoSum(int[] numbers, int target) {
+            for (int i = 0; i < numbers.length - 1; i++) {
+                int[] ans = new int[2];
+                ans[0] = i + 1;
+                int index = Arrays.binarySearch(Arrays.copyOfRange(numbers, i, numbers.length), target - numbers[i]);
+                if (index > 0) {
+                    ans[1] = index + 1 + i;
+                    return ans;
+                } else if (index == 0) {
+                    ans[1] = index + 2 + i;
+                    return ans;
+                }
+            }
+            return null;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_167Test.java b/src/test/java/com/fishercoder/_167Test.java
@@ -8,18 +8,55 @@
 
 public class _167Test {
     private static _167.Solution1 solution1;
+    private static _167.Solution2 solution2;
+    private static _167.Solution3 solution3;
     private static int[] numbers;
     private static int[] expected;
+    private int target;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _167.Solution1();
+        solution2 = new _167.Solution2();
+        solution3 = new _167.Solution3();
     }
 
     @Test
     public void test1() {
         numbers = new int[]{-3, 3, 4, 90};
         expected = new int[]{1, 2};
-        assertArrayEquals(expected, solution1.twoSum(numbers, 0));
+        target = 0;
+        assertArrayEquals(expected, solution1.twoSum(numbers, target));
+        assertArrayEquals(expected, solution2.twoSum(numbers, target));
+        assertArrayEquals(expected, solution3.twoSum(numbers, target));
+    }
+
+    @Test
+    public void test2() {
+        expected = new int[]{2, 3};
+        target = 100;
+        assertArrayEquals(expected, solution1.twoSum(new int[]{5, 25, 75}, target));
+        assertArrayEquals(expected, solution2.twoSum(new int[]{5, 25, 75}, target));
+        assertArrayEquals(expected, solution3.twoSum(new int[]{5, 25, 75}, target));
+    }
+
+    @Test
+    public void test3() {
+        numbers = new int[]{1, 2, 3, 4, 4, 9, 56, 90};
+        expected = new int[]{4, 5};
+        target = 8;
+        assertArrayEquals(expected, solution1.twoSum(numbers, target));
+        assertArrayEquals(expected, solution2.twoSum(numbers, target));
+        assertArrayEquals(expected, solution3.twoSum(numbers, target));
+    }
+
+    @Test
+    public void test4() {
+        numbers = new int[]{2, 3, 4};
+        expected = new int[]{1, 3};
+        target = 6;
+        assertArrayEquals(expected, solution1.twoSum(numbers, target));
+        assertArrayEquals(expected, solution2.twoSum(numbers, target));
+        assertArrayEquals(expected, solution3.twoSum(numbers, target));
     }
 }
