15.三数之和

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

// @lc code=start
function threeSum(nums: number[]): number[][] {
    if (nums.length < 3) {
        return [];
    }
	nums = nums.sort((a, b) => a - b);
	let res: number[][] = [];
	for (let k = 0; k < nums.length - 2; k++) {
		if (nums[k] > 0 || nums[k] == nums[k - 1]) {
			continue;
		}
		let l = k + 1,
			r = nums.length - 1;

		while (l < r) {
			if (nums[k] + nums[l] + nums[r] > 0) {
				r--;
			} else if (nums[k] + nums[l] + nums[r] < 0) {
				l++;
			} else {
				res.push([nums[k], nums[l], nums[r]]);

				while (l < r && nums[l + 1] == nums[l]) l++;
				while (l < r && nums[r - 1] == nums[r]) r--;
				l++;
				r--;
			}
		}
	}
	return res;
}

threeSum([-1,0,1,2,-1,-4]);
// @lc code=end