259. 3Sum-Smaller

difficulty: Medium

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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?

Method One

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count = 0;

        for(int i = 0; i < nums.length - 2; i++ ) {
            int aTarget = target - nums[i];
            int left = i + 1;
            int right = nums.length - 1;
            // 这里我们不需要考虑重复的了，因为只要的是不同的index组合。
            while(left < right) {
                int sum = nums[left] + nums[right];
                if(sum < aTarget){
                    // 这里是知道，一旦比 target 小，那么right一路向下到 left + 1 就有 right - left 种了。
                    // 因此直接 += right - left; 非常机智
                    count += right - left;
                    left++;
                }else{
                    right--;
                }
            }
        }

        return count;
    }
}
​