259. 3Sum Smaller

🟠   🔖  数组 双指针 二分查找 排序  🔗 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;
};