[LeetCode] 18. 4Sum

轉自LeetCode

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: 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]
]

<Solution>

這題和 3Sum 思路是一樣的

只是變成4個數，且 target 可以指定

所以在原本的架構上，再多一層 for 迴圈

以及要拿掉一些檢查條件，像是不用檢查是不是為正數，因為 target 有可能是正的

code 如下

c++

	class Solution {
	public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
	vector<vector<int>> ans;
	//>> sort first
	sort(nums.begin(), nums.end());
	const int len = nums.size();
	const int total = len - 3;
	const int secondTotal = len - 2;
	int targetSum, sum;
	int left, right;
	for(int i = 0; i < total; i++) {
	//> skip duplicate
	if(i > 0 && nums[i] == nums[i-1]) {
	continue;
	}
	for(int j = i+1; j < secondTotal; j++) {
	//> skip duplicate
	if(j > (i+1) && nums[j] == nums[j-1]) {
	continue;
	}
	targetSum = target - nums[i] - nums[j];
	left = j + 1;
	right = len - 1;
	while(left < right) {
	sum = nums[left] + nums[right];
	if(sum == targetSum) {
	ans.push_back({nums[i], nums[j], nums[left++], nums[right--]});
	//> skip duplicate
	while(left < right && nums[left] == nums[left-1]) {
	++left;
	}
	while(left < right && nums[right] == nums[right+1]) {
	--right;
	}
	}
	else if(sum < targetSum) {
	++left;
	}
	else {
	--right;
	}
	}
	}
	}
	return ans;
	}
	};

view raw fourSum.cpp hosted with ❤ by GitHub

Java

	public class Solution {
	public List<List<Integer>> fourSum(int[] nums, int target) {
	List<List<Integer>> ans = new ArrayList<>();
	//>> sort first
	Arrays.sort(nums);
	final int len = nums.length;
	final int total = len - 3;
	final int secondTotal = len - 2;
	int targetSum, sum;
	int left, right;
	for(int i = 0; i < total; i++) {
	//>> avoid duplicates
	if(i > 0 && nums[i] == nums[i-1]) {
	continue;
	}
	for(int j = i+1; j < secondTotal; j++) {
	//>> avoid duplicates
	if(j > (i+1) && nums[j] == nums[j-1]) {
	continue;
	}
	targetSum = target - nums[i] - nums[j];
	left = j + 1;
	right = len - 1;
	while(left < right) {
	sum = nums[left] + nums[right];
	if(sum == targetSum) {
	ans.add(Arrays.asList(nums[i], nums[j], nums[left++], nums[right--]));
	//>> avoid duplicates
	while(left < right && nums[left] == nums[left-1]) {
	++left;
	}
	while(left < right && nums[right] == nums[right+1]) {
	--right;
	}
	}
	else if(sum < targetSum) {
	++left;
	}
	else {
	--right;
	}
	}
	}
	}
	return ans;
	}
	}

view raw fourSum.java hosted with ❤ by GitHub