Added task 16.

javadev · javadev · commit 51a5bbdbcedf · 2021-08-01T16:51:47.000+03:00
diff --git a/src/main/java/s0016.three.sum.closest/Solution.java b/src/main/java/s0016.three.sum.closest/Solution.java
@@ -0,0 +1,41 @@
+package s0016.three.sum.closest;
+
+import java.util.Arrays;
+
+public class Solution {
+    public int threeSumClosest(int[] nums, int target) {
+        if (nums == null || nums.length < 3) return 0;
+        if (nums.length == 3) return nums[0] + nums[1] + nums[2];
+        Arrays.sort(nums);
+        int n = nums.length;
+        int sum = nums[0] + nums[1] + nums[2];
+        for (int i = 0; i < n - 2; i++) {
+            if (nums[i] + nums[n - 1] + nums[n - 2] < target) {
+                sum = nums[i] + nums[n - 1] + nums[n - 2];
+                continue;
+            }
+            if (nums[i] + nums[i + 1] + nums[i + 2] > target) {
+                int temp = nums[i] + nums[i + 1] + nums[i + 2];
+                return lessGap(sum, temp, target);
+            }
+            int j = i + 1;
+            int k = n - 1;
+            while (j < k) {
+                int temp = nums[i] + nums[j] + nums[k];
+                if (temp == target) return target;
+                if (temp < target) {
+                    j++;
+                    sum = lessGap(sum, temp, target);
+                } else {
+                    k--;
+                    sum = lessGap(sum, temp, target);
+                }
+            }
+        }
+        return sum;
+    }
+
+    private int lessGap(int sum, int temp, int target) {
+        return Math.abs(sum - target) < Math.abs(temp - target) ? sum : temp;
+    }
+}
diff --git a/src/test/java/s0016.three.sum.closest/SolutionTest.java b/src/test/java/s0016.three.sum.closest/SolutionTest.java
@@ -0,0 +1,13 @@
+package s0016.three.sum.closest;
+
+import static org.hamcrest.CoreMatchers.equalTo;
+import static org.hamcrest.MatcherAssert.assertThat;
+
+import org.junit.Test;
+
+public class SolutionTest {
+    @Test
+    public void threeSum() {
+        assertThat(new Solution().threeSumClosest(new int[] {-1, 2, 1, -4}, 1), equalTo(2));
+    }
+}
