LeetCode - Medium - 18. 4Sum

àì夳堔傛蜴生んèń 2023-01-01 13:50 84阅读 0赞

## Topic ##

*  Array
 *  Hash Table
 *  Two Pointers

## Description ##

[https://leetcode.com/problems/4sum/][https_leetcode.com_problems_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.

**Notice** that the solution set must not contain duplicate quadruplets.

**Example 1**:

Input: nums = [1,0,-1,0,-2,2], target = 0
    Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

**Example 2**:

Input: nums = [], target = 0
    Output: []

**Constraints**:

*  0 <= nums.length <= 200
 *  \-10⁹ <= nums\[i\] <= 10⁹
 *  \-10⁹ <= target <= 10⁹

## Analysis ##

**General Idea**  
If you have already read and implement the 3sum and 4sum by using the sorting approach: reduce them into 2sum at the end, you might already got the feeling that, all ksum problem can be divided into two problems:

1.  2sum Problem
2.  Reduce K sum problem to K – 1 sum Problem

Therefore, the ideas is simple and straightforward. We could use recursive to solve this problem. Time complexity is O(N^(K-1)).

## Submission ##

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class FourSum { 
    	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;
    	}
    }

## Test ##

import static org.junit.Assert.*;
    
    import java.util.Arrays;
    
    import static org.hamcrest.collection.IsIterableContainingInAnyOrder.containsInAnyOrder;
    
    import org.hamcrest.collection.IsEmptyCollection;
    import org.junit.Test;
    
    public class FourSumTest { 
    
    	@Test
    	@SuppressWarnings("unchecked")
    	public void test() { 
    		FourSum obj = new FourSum();
    
    		assertThat(obj.fourSum(new int[] { }, 0), IsEmptyCollection.empty());
    		assertThat(obj.fourSum(new int[] {  1, 0, -1, 0, -2, 2 }, 0), containsInAnyOrder(Arrays.asList(-2, -1, 1, 2),
    				Arrays.asList(-2, 0, 0, 2), Arrays.asList(-1, 0, 0, 1)));
    	}
    }

[https_leetcode.com_problems_4sum]: https://leetcode.com/problems/4sum/