259. 3Sum Smaller

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.

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?

Thoughts

对给定数组统计满足和小于target的三元组个数。2 Sum。排序并遍历i，在[0, i - 1]范围内维持首尾双指针l和r，[l, r]看作当前问题范围，当它俩加起来< target - nums[i]时说明[l+1, r]所有数都能和nums[l]拼成合法对，res += r - l，跳过l；否则说明[l, r - 1]中任何数都不能和nums[r]组成合法对，r--。

Code

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = 0
        for i, num in enumerate(nums):
            j, k = 0, i - 1
            while j < k:
                if nums[j] + nums[k] < target - num:
                    res += k - j
                    j += 1
                else:
                    k -= 1
        return res

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        int res = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            int t = target - nums[i];
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                if (nums[l] + nums[r] < t) {
                    res += r - l;
                    l++;
                } else {
                    r--;
                }
            }
        }

        return res;
    }
}

Analysis

时间复杂度O(N^2).