Question 259.
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?

题目分析

tag

类别是 arrays and strings，特点是连续存储空间中 members 的调度。

题目

本题要在连续存储空间中寻找 3 个元素，要求 3 个元素的和小于目标值的个数。

思路

示例：
nums = [-2, 0, 1, 3]
target = 2

1. 延续 No.16 的解法，当时思路是先排序，然后通过最小指针和最大指针寻找符合条件的三个数的组合。本题在此基础之上，只要变换符合的条件即可，从接近目标值，变为判断是否小于目标值，并记录符合条件的组合个数。
   首先排序，nums = [-2, 0, 1, 3]；
   取第一个元素 -2，最小指针指向 0，最大指针指向 3，和是 -2 + 0 + 3 = 1，小于目标值 2，最大指针向左移动的所有可能都符合条件，所以不用每次再做判断，这时计算最大指针到最小指针的距离即可，最大指针 index 是 3，最小指针 index 是 1，3 - 1 = 2，记录符合条件组合的个数 2；
   再取第二个元素 0，最小指针指向 1，最大指针指向 3，和是 0 + 1 + 3 = 4，大于目标值 2，最大指针向左移动，与最小指针相遇，本次结束；
   第三个元素后面只剩余一个元素，终止。
   所以符合要求的组合个数是 2，算法复杂度和 No.16 一样，O(n^2)，达到了题目的最严格要求。

Python

import sys
from typing import List

def three_sum_smaller(nums: List[int], target: int) -> int:
    # array 排序  
    nums.sort()
    # 初始化符合条件的个数为 0
    count = 0
    length = len(nums)
    # 三个数之和，所以遍历到倒数第三个数
    for i in range(length)[:-2]:
        # 如果第一个数已经大于目标值，则跳出循环
        if nums[i] >= target:
            break
        # 当前值下一个是最小指针, array 最后一个是最大指针
        left, right = i + 1, length - 1
        # 最小最大指针相交前不断循环
        while left < right:
            # 当前三个数的和
            current_sum = nums[i] + nums[left] + nums[right]
            # 如果当前和大于等于目标值，则最大值指针左移
            if current_sum >= target:
                right -= 1
            else:
                # 小于目标值，则计算最大最小值距离，加到符合个数的统计中
                count += right - left
                break
    return count

Java

import java.util.Arrays;

public int solution(int[] nums, int target) {
    // array 排序
    Arrays.sort(nums);
    # 初始化符合条件的个数为 0
    int count = 0;
    # 三个数之和，所以遍历到倒数第三个数
    for (int i = 0; i < nums.length - 2; i++) {
        # 如果第一个数已经大于目标值，则跳出循环
        if (nums[i] >= target) {
            break;
        }
        # 当前值下一个是最小指针, array 最后一个是最大指针
        int left = i + 1;
        int right = nums.length - 1;
        # 最小最大指针相交前不断循环
        while (left < right) {
            # 当前三个数的和
            int currentSum = nums[i] + nums[left] + nums[right];
            # 如果当前和大于等于目标值，则最大值指针左移
            if (currentSum >= target) {
                right -= 1;
            } else {
                # 小于目标值，则计算最大最小值距离，加到符合个数的统计中
                count += right - left;
                break;
            }
        }
    }
    return count;
}

相关题目

LeetCode 1. Two Sum
LeetCode 167. Two Sum II
LeetCode 170. Two Sum III
LeetCode 15. Three Sum
LeetCode 16. Three Sum Closest