Question

Formatted question description: https://leetcode.ca/all/18.html

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

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

@tag-array

Algorithm

Sort the original array, and then start traversing the sorted array. Note that the traversal is not to the last stop, but to the third from the bottom. Here you can do a pruning optimization first, that is, break when traversing to a positive number, why, because the array is now ordered, if the first number to be fixed is a positive number, then the following numbers

If they are all positive numbers, the sum will never be zero. Then add the process of skipping if repeated. The processing method is to start with the second number.

If it is equal to the previous number, skip it because you don’t want to fix the same number twice. For the traversed number, subtract the fix number from 0 to get a target, and then only need to find the sum of the two numbers is equal to the target.

Use two pointers to point to the first and last two numbers of the array starting after the fix number. If the sum of the two numbers happens to be the target, then the two numbers and the fix number are stored in the result together. Then is to skip the step of repeating numbers. Both pointers need to detect repeated numbers. If the sum of the two numbers is less than the target, move the pointer i on the left one bit to the right to increase the number pointed to. In the same way, if the sum of the two numbers is greater than the target, move the pointer j on the right to the left to reduce the number pointed to.

Code

Java

// general solution, k-sum
// https://leetcode.com/problems/4sum/solution/
class Solution {

	public List<List<Integer>> fourSum(int[] nums, int target) {
		Arrays.sort(nums);
		return kSum(nums, target, 0, 4);
	}

	public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
		List<List<Integer>> res = new ArrayList<>();
		if (start == nums.length || nums[start] * k > target || target > nums[nums.length - 1] * k)
			return res;
		if (k == 2)
			return twoSum(nums, target, start);
		for (int i = start; i < nums.length; ++i)
			if (i == start || nums[i - 1] != nums[i]) // 'i == start' is key, since it could be in a following recurion of [1,1,1] where start is 3rd '1'
				for (List<Integer> set : kSum(nums, target - nums[i], i + 1, k - 1)) {
					res.add(new ArrayList<>(Arrays.asList(nums[i])));
					res.get(res.size() - 1).addAll(set);
				}
		return res;
	}

	public List<List<Integer>> twoSum(int[] nums, int target, int start) {
		List<List<Integer>> res = new ArrayList<>();
		int lo = start, hi = nums.length - 1;
		while (lo < hi) {
			int sum = nums[lo] + nums[hi];
			if (sum < target || (lo > start && nums[lo] == nums[lo - 1]))
				++lo;
			else if (sum > target || (hi < nums.length - 1 && nums[hi] == nums[hi + 1]))
				--hi;
			else
				res.add(Arrays.asList(nums[lo++], nums[hi--]));
		}
		return res;
	}
}
public class Four_Sum {

    public static void main(String[] args) {
        Four_Sum out = new Four_Sum();
        Solution s = out.new Solution();
//		SolutionForLoop s= out.new SolutionForLoop();

        List<List<Integer>> result = s.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0);

        for (List<Integer> each : result) {
            String one = "";

            for (int e : each) {
                one = one + " " + e;
            }

            System.out.println(one);
        }
    }

    // time: O(NlogN)
    // space: O(1)
    public class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {

            List<List<Integer>> list = new ArrayList<>();

            if (nums.length < 4) {
                return list;
            }

            Arrays.sort(nums);

            // improved based on 3-sum
            int layer4 = 0;
            while (layer4 < nums.length) {

                // @note: below is causing me trouble when convert for to while
                // 			in while, here "layer4" is never updated for case like {0,0,0,0}
                // if(layer4 > 0 && nums[layer4] == nums[layer4 - 1]) continue;
                if (layer4 > 0 && nums[layer4] == nums[layer4 - 1]) {
                    layer4++;
                }

                // hold one pointer, other two pointer moving
                int ancher = layer4 + 1;
                while (ancher < nums.length) {

                    int i = ancher + 1;
                    int j = nums.length - 1;

                    while (i < j) {

                        int sum = nums[layer4] + nums[ancher] + nums[i] + nums[j];

                        if (sum == target) {

                            // @note: Arrays.asList()
                            list.add(Arrays.asList(nums[layer4], nums[ancher], nums[i], nums[j]));

                            // @note: dont forget move pointers
                            i++;
                            j--;

                            // @note: optimization. above i,j is updated already, compare with previous position
                            while (i < j && nums[i] == nums[i - 1]) {
                                i++;
                            }
                            while (j > i && nums[j] == nums[j + 1]) {
                                j--;
                            }

                        } else if (sum < target) {
                            i++;

                            // @note: same here, possibly updated already, note i-1 or i+1
                            while (i < j && nums[i] == nums[i - 1]) {
                                i++;
                            }

                        } else {
                            j--;

                            // @note: same here, possibly updated already, note i-1 or i+1
                            while (j > i && j + 1 < nums.length && nums[j] == nums[j + 1]) {
                                j--;
                            }

                        }
                    }

                    ancher++;

                    // optimize for 2nd pointer
                    while (ancher > layer4 && ancher < nums.length && nums[ancher] == nums[ancher - 1]) {
                        ancher++;
                    }

                }

                layer4++;

                // optimize for 2nd pointer
                while (layer4 < nums.length && nums[layer4] == nums[layer4 - 1]) {
                    layer4++;
                }
            }

            return list;
        }
    }
}

All Problems

All Solutions