力扣（LeetCode）259. 较小的三数之和（2022.09.16）

给定一个长度为 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）
链接：https://leetcode.cn/problems/3sum-smaller

方法一：双指针

C++提交内容：

class Solution {
public:
    // 将三数之和转化为两数之和
    int threeSumSmaller(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());     //对数组进行排序
        int n = nums.size(), ans = 0;
        for (int first = 0; first <= n - 3; first++) {  //确定第一个数
            if (nums[first] >= 0 && nums[first] >= target) break; //不满足条件,跳出
            int low = first + 1, high = n - 1;      //第二个与第三个数
            int twoSum = target - nums[first];  //两数之和需小于 twoSum
            while (low < high) {
                if (nums[low] + nums[high] < twoSum) { 
                    ans += (high - low);
                    low++;
                } else {
                    high--;
                }
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23