题目

题目描述

给定一个长度为 n 的整数数组和一个目标值 target ，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。

示例 1：

输入: nums = [-2,0,1,3], target = 2
输出: 2 
解释: 因为一共有两个三元组满足累加和小于 2:
     [-2,0,1]
     [-2,0,3]

示例 2：

输入: nums = [], target = 0
输出: 0 

示例 3：

输入: nums = [0], target = 0
输出: 0 

提示:

n == nums.length 0 <= n <= 3500 -100 <= nums[i] <= 100 -100 <= target <= 100

前言

这道题作为 leetcode 的第 259 道题，和 T015 T016 应该有一定的关系。

大概思路可以有下面几种：

暴力解法
数组排序+二分
Hash 优化
双指针

v1-暴力解法

思路

直接 3 次循环，找到符合结果的数据返回。

这种最容易想到，一般工作中也是我们用到最多的。

实现

public int threeSumSmaller(int[] nums, int target) {
    final int n = nums.length;
    int count = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i+1; j < n; j++) {
            for(int k = j+1; k < n; k++) {
                int sum = nums[i]+nums[j]+nums[k];
                if(sum > target) {
                    count++;
                }
            }
        }
    }
    return count;
}

效果

加密题，暂时未做真实验证。

小结

这里慢在三层循环，可以考虑排序后利用双指针优化。

可以参考 T015/T016 的思路。

v2-排序+双指针

思路

首先排序

固定第一个元素，然后后面两个元素通过双指针寻找，类似于 T015

实现

public int threeSumSmaller(int[] nums, int target) {
    Arrays.sort(nums);

    // 处理双指针
    final int n = nums.length;
    int count = 0;
    for(int i = 0; i < n-2; i++) {
        int left = i+1;
        int right = n-1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if(sum < target) {
                // 此时，在左右中的任何一个元素都满足条件
                // 但是这里不会重复吗？
                count += right-left;
                left++;
            } else {
                right--;
            }
        }
    }

    return count;
}