259.较小的三数之和

/*
 * @lc app=leetcode.cn id=259 lang=typescript
 *
 * [259] 较小的三数之和
 */

// @lc code=start
function threeSumSmaller(nums: number[], target: number): number {
	// 先规避特殊情况
	if (nums.length < 3) return 0;
	// 进行归并排序升序
	let sortNums = mergeSort(nums);
	let result: number = 0;
	for (let l = 0; l < sortNums.length - 2; l++) {
		if (
			sortNums[l] > target &&
			(l === sortNums.length - 3 || sortNums[l + 1] >= 0)
		)
			break; // 减枝
		let k = l + 1;
		let r = sortNums.length - 1;

		while (k < r) {
			let sum = sortNums[l] + sortNums[k] + sortNums[r];
			if (sum < target) {
				result += r - k;
				k++;
			} else {
				r--;
			}
		}
	}
	return result;
}

// 归并排序
function mergeSort(nums: number[]): number[] {
	if (nums.length <= 1) return nums;
	// 拆分
	let mid = Math.floor(nums.length / 2);
	let left = nums.slice(0, mid);
	let right = nums.slice(mid);
	return merge(mergeSort(left), mergeSort(right));
}

function merge(left: number[], right: number[]): number[] {
	let result: number[] = [],
		leftIndex = 0,
		rightIndex = 0;
	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] > right[rightIndex]) {
			result.push(right[rightIndex]);
			rightIndex++;
		} else {
			result.push(left[leftIndex]);
			leftIndex++;
		}
	}

	// 防止左边或右边有一个遍历完成后另外一个未完成
	return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

console.log(
	threeSumSmaller(
		[0, -2, -2, -4, 4, 3, 1, -2, -5, 1, 0, -5, -4, 4, 0, -4],
		-4
	)
);

// @lc code=end