259. 较小的三数之和 🔒

🟠   🔖  数组 双指针 二分查找 排序  🔗 力扣 LeetCode

题目

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(n^2) runtime?

题目大意

给定一个数组 nums，要求返回三数之和小于一个目标值的情况的个数。

解题思路

• 这道题是 3Sum 问题的一个变形，与 第 15 题、第 16 题 类似，不过此题不需要排除数值相等的情况。
• 也可以使用对撞指针；
• 先将数组排序，i 从后往前扫描，j，k 两个指针开始一前一后对撞，j 从数组首位开始，k 为 i 的前一个数字；
• 若三数之和大于等于 target，则 k 向左移动，继续判断；
• 若三数之和小于 target，则 j 与 k 之间的所有数做为 k，都满足 nums[i] + nums[j] + nums[k] < target，此时将 j 向右移动，继续判断；

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumSmaller = function (nums, target) {
	nums = nums.sort((a, b) => a - b);
	const len = nums.length;
	let res = 0;
	for (let i = len - 1; i > 1; i--) {
		let j = 0;
		let k = i - 1;
		while (j < k) {
			let sum = nums[i] + nums[j] + nums[k];
			if (sum >= target) {
				k--;
			} else {
				res += k - j;
				j++;
			}
		}
	}
	return res;
};