refactor 220

fishercoder1534 · fishercoder1534 · commit 6b54d9058b75 · 2019-12-31T09:03:31.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_220.java b/src/main/java/com/fishercoder/solutions/_220.java
@@ -4,7 +4,7 @@
 
 /**
  * 220. Contains Duplicate III
- * <p>
+ *
  * Given an array of integers, find out whether there are two
  * distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at
  * most t and the difference between i and j is at most k.
@@ -22,15 +22,13 @@ public static class Solution1 {
         /**
          * TreeSet turns out to be a super handy data structure for this problem. It implements Set
          * interface and keeps elements in sorted order, plus it has two very handy APIs:
-         * <p>
          * https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#ceiling(E): Returns the
          * least element in this set greater than or equal to the given element, or null if there is no
          * such element.
-         * <p>
          * https://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html#floor(E): Returns the
          * greatest element in this set less than or equal to the given element, or null if there is no
          * such element.
-         * <p>
+         *
          * Idea: loop through this array, keep adding each element into the TreeSet, also keep an eye on
          * the size of the TreeSet, if it's greater than the required distance of k, then we remove the
          * left-most or oldest one from the set. For each element, we get the current floor and the
@@ -39,23 +37,22 @@ public static class Solution1 {
          */
 
         public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
-            TreeSet<Integer> set = new TreeSet<>();
+            /**case to Long to avoid Integer overflow.*/
+            TreeSet<Long> set = new TreeSet<>();
             for (int i = 0; i < nums.length; ++i) {
-                // Find the successor of current element
-                Integer s = set.ceiling(nums[i]);
-                if (s != null && s <= nums[i] + t) {
+                Long s = set.ceiling((long) nums[i]);
+                if (s != null && s - nums[i] <= t) {
                     return true;
                 }
 
-                // Find the predecessor of current element
-                Integer g = set.floor(nums[i]);
-                if (g != null && nums[i] <= g + t) {
+                Long g = set.floor((long) nums[i]);
+                if (g != null && nums[i] - g <= t) {
                     return true;
                 }
 
-                set.add(nums[i]);
+                set.add((long) nums[i]);
                 if (set.size() > k) {
-                    set.remove(nums[i - k]);
+                    set.remove((long) nums[i - k]);
                 }
             }
             return false;
diff --git a/src/test/java/com/fishercoder/_220Test.java b/src/test/java/com/fishercoder/_220Test.java
@@ -51,4 +51,10 @@ public void test6() {
         assertEquals(false, solution1.containsNearbyAlmostDuplicate(nums, 1, 2147483647));
     }
 
+    @Test
+    public void test7() {
+        nums = new int[]{-1, 2147483647};
+        assertEquals(false, solution1.containsNearbyAlmostDuplicate(nums, 1, 2147483647));
+    }
+
 }

Original file line number	Diff line number	Diff line change
`@@ -51,4 +51,10 @@ public void test6() {`
`51`	`51`	`assertEquals(false, solution1.containsNearbyAlmostDuplicate(nums, 1, 2147483647));`
`52`	`52`	`}`
`53`	`53`
	`54`	`+ @Test`
	`55`	`+ public void test7() {`
	`56`	`+ nums = new int[]{-1, 2147483647};`
	`57`	`+ assertEquals(false, solution1.containsNearbyAlmostDuplicate(nums, 1, 2147483647));`
	`58`	`+ }`
	`59`	`+`
`54`	`60`	`}`