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.

Example:

Input:
nums
 = 
[-2,0,1,3]
, and 
target
 = 2

Output:
 2 

Explanation:
 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?

Solution

(1) Java

class Solution {

    public int threeSumSmaller(int[] nums, int target) {
        int rst = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-2; i++) {
            int j = i+1;
            int k = nums.length-1;
            while (j < k) {
                int num = nums[j]+nums[k]+nums[i];
                if (num < target) {
                    rst += k-j;
                    j++;
                } else {
                    k--;
                }
            }
        }
        return rst;
    }
}

(2) Python

(3) Scala