4Sum

LeetCode Q 18 - 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target?Find all unique quadruplets in the array which gives the sum of target.

Note:The solution set must not contain duplicate quadruplets.

Solution

The key points are, 1) how we deal with duplicates, 2) how to make use of boundary case to make our code more effecient.

Code:

public List<List<Integer>> fourSum(int[] nums, int target) {
	List<List<Integer>> res = new ArrayList<>();
	int len = nums.length;
	Arrays.sort(nums);
	if (len < 4 || nums[0] * 4 > target || nums[len - 1] * 4 < target)
		return res;

	for (int i = 0; i < nums.length - 3; i++) {
		if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; // i is too large;
		if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target) continue; // i is too small;
		if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates
		for (int j = i + 1; j < nums.length - 2; j++) {
			if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break; // j is too large;
			if (nums[i] + nums[j] + nums[len - 1] + nums[len - 2] < target) continue; // j is too small;
			if (j > i + 1 && nums[j] == nums[j - 1]) continue; // skip duplicates
			
			int start = j + 1, end = len - 1;
			while (start < end) {
				int sum = nums[i] + nums[j] + nums[start] + nums[end];
				if (sum == target) {
					res.add(Arrays.asList(nums[i], nums[j], nums[start], nums[end]));
					while (start < end && nums[start] = nums[start+1]) start++;
					while (start < end && nums[end] = nums[end-1]) end--;
					start++; end--;
				}
				else if (sum > target) end--;
				else start++;
			}
		}
	}
	return res;
}