18.四数之和

/*
 * @lc app=leetcode.cn id=18 lang=typescript
 *
 * [18] 四数之和
 */

// @lc code=start
function fourSum(nums: number[], target: number): number[][] {
	if (nums.length < 4) return [];
	// 先从小到大排序
	nums.sort((a, b) => a - b);
	// 记录结果
	let res: number[][] = [];
	// 标记k1
	let k1 = 0;
	while (k1 < nums.length - 3) {
		// 标记k2
		let k2 = k1 + 1;
		while (k2 < nums.length - 2) {
			// 标记l、r
			let l = k2 + 1;
			let r = nums.length - 1;

			while (l < r) {
				if (nums[k1] + nums[k2] + nums[l] + nums[r] > target) {
					r--;
				} else if (nums[k1] + nums[k2] + nums[l] + nums[r] < target) {
					l++;
				} else {
					// 记录结果
					res.push([nums[k1], nums[k2], nums[l], nums[r]]);
					// 排除重复选项
					while (l < r && nums[l] == nums[l + 1]) l++;
					while (l < r && nums[r] == nums[r - 1]) r--;
					// 移动坐标
					l++;
					r--;
				}
			}
			k2++;
			while (nums[k2] == nums[k2 - 1]) k2++;
		}
		k1++;
		while (nums[k1] == nums[k1 - 1]) k1++;
	}
	console.log(res);
	return res;
}

fourSum([2, 2, 2, 2, 2], 8);
// @lc code=end