202410182122
tags: #hash-map

var fourSum = function(nums, target) {
	nums.sort((a, b) => a - b);
	const res = [];
	for (let i = 0; i < nums.length - 3; i++) {
		if (i > 0 && nums[i] === nums[i - 1]) {
			continue;
		}
		for (let j = i + 1; j < nums.length - 2; j++) {
			if (j > i + 1 && nums[j] === nums[j - 1]) {
				continue;
			}
			let start = j + 1;
			let end = nums.length - 1;
			while (start < end) {
				const sum = nums[i] + nums[j] + nums[start] + nums[end];
				if (sum === target) {
					res.push([nums[i], nums[j], nums[start], nums[end]]);
					while (start < end && nums[start] === nums[start + 1]) {
						start += 1;
					}
					while (start < end && nums[end] === nums[end - 1]) {
						end -= 1;
					}
					start += 1;
					end -= 1;
				}
				else if (sum < target) {
					start += 1;
				}
				else {
					end -= 1;
				}
			}
		}
	}
	return res;
};

Reference

https://leetcode.com/problems/4sum/