Leetcode/G家 -- 259. 3Sum Smaller (3 ptr)

259. 3Sum Smaller (3 ptr)
Medium
https://leetcode.com/problems/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]

思路： like three sum. When calculating count, if sum < target, count += k-j since nums[i] + nums[j] + elements after k will also have sum<target.

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int count = 0;
        Arrays.sort(nums);
        for (int i = 0; i + 2 < nums.length; i++) {
            int j = i + 1, k = nums.length - 1;  
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < target) {
                    count += k-j;//eg [-2,0,1,3] 4,so -2,0,3满足，-2,0,1也满足
                    j++;
                } else {
                    k--;
                }
            }
        }
        return count;
    }
}