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.
Example:
Given array nums = [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]
]
Solution
(1) Java
Do as a n sum solution. For 4sum, the time complexity is O(n^3). For ksum, the time complexity is O(N^(K-1)), how to get it?
suppose T(n, k) denotes the time complexity required to compute a Ksum problem for an sorted array of size n. the base cases are
T(n, 1) = n
T(n, 2) = n
now for every other k we would have to loop once through the array and check if the k-1 sum is possible from the other elements so
T(n, 3) = n*T(n, 2)
T(n, 4) = n*T(n, 3)
....
T(n, k) = n*T(n, k-1)
so for k>2 the time complexity would be
O(n^(k-1))
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
if (nums == null || nums.length <= 3) {
return rst;
}
Arrays.sort(nums);
nsum(4, 0, 0, new ArrayList<Integer>(), nums, target, rst);
return rst;
}
private void nsum(int n, int startIdx, int partialSum, List<Integer> partialList, int[] nums, int target, List<List<Integer>> rst) {
if (n == 2) {
int left = startIdx;
int right = nums.length-1;
while (left < right) {
int sum = nums[left]+nums[right]+partialSum;
if (sum == target) {
List<Integer> list = new ArrayList(partialList);
list.add(nums[left]);
list.add(nums[right]);
rst.add(list);
while (left < right && nums[left] == nums[left+1]) {
left++;
}
while (left < right && nums[right] == nums[right-1]) {
right--;
}
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
} else {
for (int i = startIdx; i <= nums.length-n; i++) {
if (i != startIdx && nums[i] == nums[i-1]) {
continue;
}
partialList.add(nums[i]);
nsum(n-1, i+1, partialSum+nums[i], partialList, nums, target, rst);
partialList.remove(partialList.size()-1);
}
}
}
}
A little imporved version:
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, 0, 4, target);
}
private List<List<Integer>> kSum (int[] nums, int start, int k, int target) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(k == 2) { //two pointers from left and right
int left = start, right = len - 1;
while(left < right) {
int sum = nums[left] + nums[right];
if(sum == target) {
List<Integer> path = new ArrayList<Integer>();
path.add(nums[left]);
path.add(nums[right]);
res.add(path);
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) { //move left
left++;
} else { //move right
right--;
}
}
} else {
for(int i = start; i < len - (k - 1); i++) {
if(i > start && nums[i] == nums[i - 1]) continue;
List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]);
for(List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
}
return res;
}
(2) Python
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
def ksum(nums, target, k):
rst = []
if (k == 2):
left, right = 0, len(nums)-1
while left < right:
total = nums[left]+nums[right]
if total == target:
rst.append([nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif total < target:
left += 1
else:
right -= 1
else:
for i in xrange(0, len(nums)-k+1):
if i != 0 and nums[i] == nums[i-1]:
continue
lists = ksum(nums[i+1:], target-nums[i], k-1)
if len(lists) > 0:
for l in lists:
l.append(nums[i])
rst.append(l)
return rst
if not nums or len(nums) <= 3:
return []
nums.sort()
return ksum(nums, target, 4)
(3) Scala
import scala.collection.mutable.ListBuffer
object Solution {
def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
val rst = ListBuffer[List[Int]]()
if (nums == null || nums.length == 0) {
return rst.toList
}
scala.util.Sorting.quickSort(nums)
ksum(nums, target, 4, 0, List[Int](), rst)
return rst.toList
}
def ksum(nums: Array[Int], target: Int, k: Int, startIdx: Int, sum: List[Int], rst: ListBuffer[List[Int]]) {
if (k == 2) {
twoSum(nums, target, startIdx, sum, rst)
} else {
for (i <- startIdx to nums.length-k) {
if (i == startIdx || nums(i) != nums(i-1)) {
ksum(nums, target-nums(i), k-1, i+1, nums(i)::sum, rst)
}
}
}
}
def twoSum(nums: Array[Int], target: Int, startIdx: Int, sum: List[Int], rst: ListBuffer[List[Int]]) {
var left = startIdx;
var right = nums.length-1
while (left < right) {
if (nums(left)+nums(right) == target) {
val list: List[Int] = nums(left)::nums(right)::sum
rst += list
while(left < right && nums(left) == nums(left+1)) {
left += 1
}
while(left < right && nums(right) == nums(right-1)) {
right -= 1
}
left += 1
right -= 1
} else if (nums(left)+nums(right) < target) {
left += 1
} else {
right -= 1
}
}
}
}