我在解决一个问题。问题如下--
给定一个由n个整数组成的数组nums和一个整数目标，nums中是否有元素a、b、c和d，使得a+b+c+d=target？在数组中找到所有唯一的四元组，它给出目标的和。
注：
解决方案集不能包含重复的四元组。
给定数组 nums = [-1,0,1,2,-1,-4] ，和 target = -1 .
解决方案集是： [[-4,0,1,2],[-1,-1,0,1]] 下面给出了解决这个问题的代码-
class Solution {
List<List<Integer>> output=new ArrayList();
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(i==0 || nums[i-1]!=nums[i]){
for(int j=i+1;j<nums.length;j++){
if(j==1 || nums[j-1]!=nums[j]){
calculate(nums, i, j, target);
}
}
}
}
return output;
}
public void calculate(int[] nums, int i, int j, int target){
Set<Integer> hashSet=new HashSet();
for(int k=j+1; k<nums.length;k++){
int vector=target-nums[i]-nums[j]-nums[k];
if(hashSet.contains(vector)){
output.add(Arrays.asList(nums[i], nums[j], nums[k],vector));
while(k+1<nums.length && nums[k]==nums[k+1]){
k++;
}
}
hashSet.add(nums[k]);
}
}}
我的输出是： [[-4,0,2,1]] 但预期产出是： [[-4,0,1,2],[-1,-1,0,1]] 请帮帮我！
要解决此问题，请执行以下步骤。。
A) For the main function:
1. Sort the input array nums.
2. Iterate through the array for 2 times (i, j):
If the current value is greater than zero, break from the
loop. Remaining values cannot sum to zero.
If the current value is the same as the one before, skip it.
Otherwise, call twoSum for the current position i.
B) For calculate function:
1. For each index k > j in A:
2. Compute complement vector = target -nums[i] - nums[j].
3. If complement exists in hashset seen:
4. We found a triplet - add it to the result res.
5. Increment k while the next value is the same as before to
avoid duplicates in the result.
C) Add nums[k] to hashset seen
D) Return the result output.
2条答案
按热度按时间jslywgbw1#
这个问题是3sum的后续问题。4sum和3sum非常相似；不同的是，我们正在寻找独特的四胞胎而不是三胞胎。
按照类似的逻辑，我们可以通过在另一个循环中 Package 4sum来实现5sum。但是6sum，7sum等等呢。我们最好还是去找ksum解决方案。下面的代码适用于2sum、3sum、4sum等等。
vaqhlq812#
问题出在第一线
(j==1 || nums[j-1]!=nums[j])&(i==0 || nums[i-1]!=nums[i])```static List<List> output;
public static void main (String[] args) throws Exception{
output = new ArrayList<>();
fourSum(new int[]{0,0,0,0},0);
System.out.println(output);
}
public static void fourSum(int[] nums, int target) {
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
calculate(nums, i, j, target);
}
}
}
public static void calculate(int[] nums, int i, int j, int target){
Set hashSet=new HashSet();
for(int k=j+1; k<nums.length;k++){
int vector=target-nums[i]-nums[j]-nums[k];
if(hashSet.contains(vector)){
output.add(Arrays.asList(nums[i], nums[j], nums[k],vector));
while(k+1<nums.length && nums[k]==nums[k+1]){
k++;
}
}
hashSet.add(nums[k]);
}
}