package com.fishercoder.solutions;

import java.util.Arrays;

/**259. 3Sum Smaller

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 _259 {

    /**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;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < target) {
                    result += right - left;//this line is key!
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

@@ -59,440 +59,88 @@
 s;%0A%0A
-/**259. 3Sum Smaller%0A%0AGiven an array of n integers nums and a target, find the number of index triplets i, j, k with 0 %3C= i %3C j %3C k %3C n that satisfy the condition nums%5Bi%5D + nums%5Bj%5D + nums%5Bk%5D %3C target.%0A%0AFor example, given nums = %5B-2, 0, 1, 3%5D, and target = 2.%0A%0AReturn 2. Because there are two triplets which sums are less than 2:%0A%0A%5B-2, 0, 1%5D%0A%5B-2, 0, 3%5D%0A%0AFollow up:%0ACould you solve it in O(n2) runtime? */%0Apublic class _259 %7B%0A%0A
+public class _259 %7B%0A%0A    public static class Solution1 %7B%0A        /**%0A     
     
-/*
 *
+ 
 Basi
@@ -266,11 +266,25 @@
 y 1!
-*/%0A
+%0A         */%0A    
     
@@ -340,24 +340,28 @@
 ) %7B%0A        
+ 
+   
 if (nums == 
@@ -396,24 +396,28 @@
             
+    
 return 0;%0A  
@@ -414,34 +414,42 @@
 turn 0;%0A        
+ 
-%7D%0A
+   %7D%0A    
         int resu
@@ -464,16 +464,20 @@
         
+ 
+   
 Arrays.s
@@ -487,16 +487,20 @@
 (nums);%0A
+    
         
@@ -551,24 +551,28 @@
             
+    
 int left = i
@@ -573,24 +573,28 @@
 ft = i + 1;%0A
+    
             
@@ -634,16 +634,20 @@
         
+    
 while (l
@@ -657,24 +657,28 @@
  %3C right) %7B%0A
+    
             
@@ -739,24 +739,28 @@
             
+    
 if (sum %3C ta
@@ -759,32 +759,36 @@
 sum %3C target) %7B%0A
+    
                 
@@ -854,16 +854,20 @@
         
+    
 left++;%0A
@@ -882,16 +882,20 @@
         
+   
+ 
 %7D else %7B
@@ -895,16 +895,20 @@
  else %7B%0A
+    
         
@@ -936,34 +936,42 @@
                 
-%7D%0A
+    %7D%0A    
             %7D%0A  
@@ -968,34 +968,42 @@
       %7D%0A        
+   
+ 
 %7D%0A
+    
         return r
@@ -1009,16 +1009,26 @@
 result;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 259