1099.小于-k-的两数之和

/*
 * @lc app=leetcode.cn id=1099 lang=typescript
 *
 * [1099] 小于 K 的两数之和
 */

// @lc code=start

/* 暴力循环法，复杂度很高 */
// function twoSumLessThanK(nums: number[], k: number): number {
// 	let max = -1;
// 	nums.map((num, index) => {
// 		let diff = k - num;
// 		nums.slice(index + 1).map(num2 => {
// 			if (num2 < diff) {
// 				if (num + num2 > max) {
// 					max = num + num2;
// 				}
// 			}
// 		});
// 	});
// 	return max; // -1表示不存在
// }

/* 双指针 */
function twoSumLessThanK(nums: number[], k: number): number {
	// 排序，从小到大
	nums = nums.sort((a, b) => a - b);
	let l = 0,
		r = nums.length - 1;
	let result = -1;
	while (l < r) {
		let currentSum = nums[l] + nums[r];
		if (currentSum >= k) {
			r--;
		} else {
			if (currentSum > result) {
				result = currentSum;
			}
			l++;
		}
	}
	return result;
}

let nums = [
		358, 898, 450, 732, 672, 672, 256, 542, 320, 573, 423, 543, 591, 280,
		399, 923, 920, 254, 135, 952, 115, 536, 143, 896, 411, 722, 815, 635,
		353, 486, 127, 146, 974, 495, 229, 21, 733, 918, 314, 670, 671, 537,
		533, 716, 140, 599, 758, 777, 185, 549,
	],
	k = 1800;

console.log(twoSumLessThanK(nums, k));

// @lc code=end