2Sum, 3Sum, 4Sum ....... kSum with HashSet(哈希表)解决方案

Question

我正在解决一个问题。问题如下--

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.

注：

解集不能包含重复的四元组。

给定数组 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.

Answer 1

问题出在行 (j==1 || nums[j-1]!=nums[j]) & (i==0 || nums[i-1]!=nums[i])

static List<List<Integer>> 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<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]);
    }
}

输入：{0,0,0,0}，target:0，输出：[[0,0,0,0]]

输入：{-1,0,1,2,-1,-4}，目标：-1，输出：[[-4, 0, 2, 1], [-1, -1, 1, 0]]

Answer 2

这道题是一道 follow-up 的 3Sum。 4Sum 和 3Sum 非常相似；不同之处在于我们正在寻找独特的四胞胎而不是三胞胎。

按照类似的逻辑，我们可以通过将4Sum包装在另一个循环中来实现5Sum。但是 6Sum、7Sum 等等呢？我们最好选择 kSum 解决方案。以下代码适用于 2Sum、3Sum、4Sum 等。

class Solution {

 public List<List<Integer>> fourSum(int[] nums, int target) {
    Arrays.sort(nums);
    int start=0;
    int k=4;
    return this.kSum(nums,target,start,k);            
 }

 public List<List<Integer>> kSum(int[] nums, int target, int start, int k){
    
    List<List<Integer>> output= new ArrayList<>();
    
    if(start==nums.length || nums[start] * k>target || nums[nums.length-1]*k<target)
        return output;
    
    if(k==2)
       return this.twoSum(nums,target,start);
    for(int i=start;i<nums.length;i++){
        if(i==start || nums[i-1]!=nums[i])
            for(var set: kSum(nums, target-nums[i],i+1,k-1)){
                output.add(new ArrayList<>(Arrays.asList(nums[i])));
                output.get(output.size()-1).addAll(set);
            }
        
    }
    return output;
    
    
 }

 public List<List<Integer>> twoSum(int[] nums, int Target, int start){
    
    
    List<List<Integer>> output=new ArrayList<>();
    Set<Integer> set=new HashSet<>();
    
    for(int i=start;i<nums.length;i++){
        if(output.isEmpty() || output.get(output.size()-1).get(1) !=nums[i]){
            int vector=Target-nums[i];
            if(set.contains(vector)){
                output.add(Arrays.asList(vector, nums[i]));
            }
        }
        set.add(nums[i]);
    }
    
    return output;
 }

}

2Sum, 3Sum, 4Sum ....... kSum with HashSet(哈希表)解决方案

2Sum, 3Sum, 4Sum ........kSum with HashSet (HashTable) solution

java

arrays

algorithm

hashtable

hashmap