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, 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 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

// general solution, k-sum
// https://leetcode.com/problems/4sum/solution/
// below kSum() divide-and-conquer idea is good, but not passing Online-Judge
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;
        }
    }
}

// OJ: https://leetcode.com/problems/4sum/
// Time: O(N^3)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& A, int target) {
        int N = A.size();
        sort(begin(A), end(A));
        vector<vector<int>> ans;
        for (int i = 0; i < N; ++i) {
            if (i > 0 && A[i] == A[i - 1]) continue;
            for (int j = i + 1; j < N; ++j) {
                if (j > i + 1 && A[j] == A[j - 1]) continue;
                int t = target - A[i] - A[j];
                for (int p = j + 1, q = N - 1; p < q; ) {
                    if (A[p] + A[q] == t) {
                        ans.push_back({ A[i], A[j], A[p++], A[q--] });
                        while (p < q && A[p] == A[p - 1]) ++p;
                        while (p < q && A[q] == A[q + 1]) --q;
                    } else if (A[p] + A[q] < t) ++p;
                    else --q;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n, res = len(nums), []
        if n < 4:
            return []
        nums.sort()
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                k, l = j + 1, n - 1
                while k < l:
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        res.append([nums[i], nums[j], nums[k], nums[l]])
                        k += 1
                        l -= 1
                        while k < n and nums[k] == nums[k - 1]:
                            k += 1
                        while l > j and nums[l] == nums[l + 1]:
                            l -= 1
                    elif nums[i] + nums[j] + nums[k] + nums[l] < target:
                        k += 1
                    else:
                        l -= 1
        return res

############

class Solution(object):
  def fourSum(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: List[List[int]]
    """
    nums.sort()
    res = []
    for i in range(0, len(nums)):
      if i > 0 and nums[i] == nums[i - 1]:
        continue
      for j in range(i + 1, len(nums)):
        if j > i + 1 and nums[j] == nums[j - 1]:
          continue
        start = j + 1
        end = len(nums) - 1
        while start < end:
          sum = nums[i] + nums[j] + nums[start] + nums[end]
          if sum < target:
            start += 1
          elif sum > target:
            end -= 1
          else:
            res.append((nums[i], nums[j], nums[start], nums[end]))
            start += 1
            end -= 1
            while start < end and nums[start] == nums[start - 1]:
              start += 1
            while start < end and nums[end] == nums[end + 1]:
              end -= 1
    return res


# todo: below solution is buggy and need further fix
class Solution:
	def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
		nums.sort()
		return self.kSum(nums, target, 0, 4)

	def kSum(self, nums: List[int], target: int, start: int, k: int) -> List[List[int]]:
		res = []

		if start ==  len(nums) or nums[start] * k > target or nums[-1] * k < target:
			return res

		if k == 2:
			return self.twoSum(nums, target, start)

		for i in range(start, len(nums)):
			if i == start or (i > 0 and nums[i] != nums[i - 1]):
				sub_res = self.kSum(nums, target - nums[start], start + 1, k - 1)
				for each in sub_res:
					each.append(nums[i])
					res.append(each)

		return res

	def twoSum(self, nums: List[int], target: int, start: int) -> List[List[int]]:
		d = {}
		for i, num in enumerate(nums):
			if target - num in d:
				return [[target - num, num]]
			d[num] = i

func fourSum(nums []int, target int) [][]int {
	ans, n := [][]int{}, len(nums)
	sort.Ints(nums)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			for l, r := j+1, n-1; l < r; {
				if nums[i]+nums[j]+nums[l]+nums[r] == target {
					ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
					l, r = l+1, r-1
					for l < r && nums[l] == nums[l-1] {
						l++
					}
					for l < r && nums[r] == nums[r+1] {
						r--
					}
				} else if nums[i]+nums[j]+nums[l]+nums[r] < target {
					l++
				} else {
					r--
				}
			}
			for j+1 < n && nums[j+1] == nums[j] {
				j++
			}
		}
		for i+1 < n && nums[i+1] == nums[i] {
			i++
		}
	}
	return ans
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {
    const n = nums.length;
    if (n < 4) return [];
    let res = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < n - 3; ++i) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (let j = i + 1; j < n - 2; ++j) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            let k = j + 1;
            let l = n - 1;
            while (k < l) {
                if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
                    res.push([nums[i], nums[j], nums[k], nums[l]]);
                    ++k;
                    --l;
                    while (k < n && nums[k] == nums[k - 1]) ++k;
                    while (l > j && nums[l] == nums[l + 1]) --l;
                } else if (nums[i] + nums[j] + nums[k] + nums[l] < target) {
                    ++k;
                } else {
                    --l;
                }
            }
        }
    }
    return res;
};

using System;
using System.Collections.Generic;
using System.Linq;

class FourSumComparer : IEqualityComparer<IList<int>>
{
    public bool Equals(IList<int> left, IList<int> right)
    {
        return left[0] == right[0] && left[1] == right[1] && left[2] == right[2] && left[3] == right[3];
    }

    public int GetHashCode(IList<int> obj)
    {
        return (obj[0] ^ obj[1] ^ obj[2] ^ obj[3]).GetHashCode();
    }
}

public class Solution {
    public IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        var results = new HashSet<IList<int>>(new FourSumComparer());
        for (var i = 0; i < nums.Length; ++i)
        {
            for (var j = i + 1; j < nums.Length; ++j)
            {
                var sum = target - nums[i] - nums[j];
                var k = j + 1;
                var l = nums.Length - 1;
                var step = (int)Math.Sqrt(nums.Length);
                while (k < l)
                {
                    while (k + step < l && nums[k + step] + nums[l] < sum)
                    {
                        k += step;
                    }
                    while (k < l && nums[k] + nums[l] < sum)
                    {
                        k += 1;
                    }
                    if (k < l && nums[k] + nums[l] == sum)
                    {
                        results.Add(new [] { nums[i], nums[j], nums[k], nums[l] });
                        ++k;
                    }
                    while (k + step < l && nums[k] + nums[l - step] > sum)
                    {
                        l -= step;
                    }
                    while (k < l && nums[k] + nums[l] > sum)
                    {
                        l -= 1;
                    }
                    if (k < l && nums[k] + nums[l] == sum)
                    {
                        results.Add(new [] { nums[i], nums[j], nums[k], nums[l] });
                        --l;
                    }
                }
            }
        }

        return results.ToList();
    }
}

18 - 4Sum

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions