英文:
2Sum, 3Sum, 4Sum ........kSum with HashSet (HashTable) solution
问题
我解决了一个问题。 问题如下 -
> *给定一个包含n个整数的数组nums和一个整数target，是否存在元素a、b、c和d在nums中，使得a + b + c + d = target？找到数组中所有使得和为target的唯一四元组。*
**注意：**
解集中不能包含重复的四元组。
给定数组`nums = [-1,0,1,2,-1,-4]`，以及`target = -1`。
一个解集是：
`[[-4,0,1,2],[-1,-1,0,1]]`
以下是我为该问题编写的代码-
```java
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）对于主函数：
- 对输入数组nums进行排序。
- 通过数组进行2次迭代（i，j）：
如果当前值大于零，则退出循环。剩余值不能相加为零。
如果当前值与前一个值相同，则跳过它。
否则，对当前位置i调用twoSum。
B）对于calculate函数：
- 对于每个索引k > j在A中：
- 计算补充向量 = target - nums[i] - nums[j]。
- 如果在hashset seen中存在补充向量：
- 我们找到了一个四元组-将其添加到结果res中。
- 在下一个值与之前的值相同时，增加k，以避免结果中的重复。
C）将nums[k]添加到hashset seen中
D）返回结果output。
<details>
<summary>英文:</summary>
I am solving a problem. The problem is given below --
> *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.
Given array `nums = [-1,0,1,2,-1,-4]`, and `target = -1`.
A solution set is:
`[[-4,0,1,2],[-1,-1,0,1]]`
My code is given below for the that problem-
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]);
}
}
}
My output is: `[[-4,0,2,1]]`
But expected output is: `[[-4,0,1,2],[-1,-1,0,1]]`
Please help!
To solve this problem following steps I have performed..
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.
</details>
# 答案1
**得分**: 2
问题出在第 `(j==1 || nums[j-1]!=nums[j])` 和 `(i==0 || nums[i-1]!=nums[i])` 行。
```java
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}，目标：0，输出：[[0,0,0,0]]
输入：{-1,0,1,2,-1,-4}，目标：-1，输出：[[-4, 0, 2, 1], [-1, -1, 1, 0]]
英文:
Problem is at line (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]);
}
}
input:{0,0,0,0}, target:0, output: [[0,0,0,0]]
input:{-1,0,1,2,-1,-4}, target:-1, output: [[-4, 0, 2, 1], [-1, -1, 1, 0]]
答案2
得分: 0
这个问题是 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;
}
}
请注意，这只是代码的翻译部分，不包括任何额外的信息。
英文:
This problem is a follow-up of 3Sum. 4Sum and 3Sum are very similar; the difference is that we are looking for unique quadruplets instead of triplets.
Following a similar logic, we can implement 5Sum by wrapping 4Sum in another loop. But what about the 6Sum, 7Sum and so on. It's better we should go for kSum solution. Following code will work for 2Sum, 3Sum, 4Sum and so on.
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;
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论