MEDIUM/src/medium/_3Sum_Smaller.java

fishercoder1534 · fishercoder1534 · commit 885b0659b8fa · 2016-09-08T13:19:40.000-07:00
diff --git a/MEDIUM/src/medium/_3Sum_Smaller.java b/MEDIUM/src/medium/_3Sum_Smaller.java
@@ -0,0 +1,42 @@
+package medium;
+
+import java.util.Arrays;
+
+/**259. 3Sum Smaller
+
+    Total Accepted: 13428
+    Total Submissions: 33743
+    Difficulty: Medium
+
+Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.
+
+For example, given nums = [-2, 0, 1, 3], and target = 2.
+
+Return 2. Because there are two triplets which sums are less than 2:
+
+[-2, 0, 1]
+[-2, 0, 3]
+
+Follow up:
+Could you solve it in O(n2) runtime? */
+public class _3Sum_Smaller {
+
+    /**Basically, very similar to 3Sum, but the key is that you'll have to add result by (right-left), not just increment result by 1!*/
+    public int threeSumSmaller(int[] nums, int target) {
+        if(nums == null || nums.length == 0) return 0;
+        int result = 0;
+        Arrays.sort(nums);
+        for(int i = 0; i < nums.length-2; i++){
+            int left = i+1, right = nums.length-1;
+            while(left < right){
+                int sum = nums[i] + nums[left] + nums[right];
+                if(sum < target) {
+                    result += right-left;//this line is super cool!
+                    left++;
+                } else right--;
+            }
+        }
+        return result;
+    }
+
+}
