题目

这是 LeetCode259 较小的三数之和 的简单版（详细思路见 259 题），其实 259 题也可以取名为：小于 K 的三数之和。所以两道题解题思路一样，259 题就是在 1099 题上套了层循环。

解题

解题一：二分查找

// javascript
var twoSumLessThanK = function(nums, k) {nums.sort((a, b) => a - b);let sum = -1;for (let i = 0; i < nums.length - 1; ++i) {const target = k - nums[i];let left = i + 1, right = nums.length - 1;while (left <= right) {const mid = left + ((right - left) >> 1);if (nums[mid] >= target) {right = mid - 1;} else {left = mid + 1;}}// 如果 [i + 1, nums.length - 1] 里找不到 > target 的数，right = i// 但是两个数字应该是不相同的，所以 i === right 时，不对 sum 进行更新if (i !== right) {sum = Math.max(sum, nums[i] + nums[right]);}}return sum;
};

时间复杂度：$O(n\log n)$。排序需要 $O(n\log n)$，枚举 $i$ 需要 $O(n)$，二分查找 $j$ 需要 $O(\log n)$，因此总的时间复杂度为 $O(n\log n)$。

空间复杂度：$O(\log n)$。排序需要 $O(\log n)$，其余变量空间都是常数范围内的。

解题二：双指针

j 是从后向前遍历的，当 nums[i] + nums[j] < k 时找到的是 [i + 1, nums.length - 1] 范围内符合条件的 j 的最大值，数组又是升序排列的，所以 nums[i] + nums[j] 就是固定左指针时能获得的最大的小于 K 的两数之和。更新 sum 值，再移动左指针去寻找有没有更大的小于 K 的两数和。

// javascript
var twoSumLessThanK = function(nums, k) {nums.sort((a, b) => a - b);let sum = -1;let i = 0, j = nums.length - 1;while (i < j) {if (nums[i] + nums[j] >= k) {j--;} else {sum = Math.max(sum, nums[i] + nums[j]);i++;}}return sum;
};

时间复杂度：$O(n\log n)$。排序需要 $O(n\log n)$，在每一步中，要么 $\mathrm{i}$ 向右移动一位，要么 $\mathrm{j}$ 向左移动一位。当 $\mathrm{i}\ge \mathrm{j}$ 时循环结束，因此它的时间复杂度为 $O(n)$。

空间复杂度：$O(\log n)$。排序需要 $O(\log n)$，其余变量空间都是常数范围内的。