leetcode 的问题陈述是这样的:
给定一个由 n 个整数组成的数组 S,S 中是否存在元素 a、b、c 和 d,使得 a + b + c + d = target?找到数组中所有唯一的四元组,给出目标的总和。
Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
关于这个四和问题,我有两个问题:
- 我哪里出错了?编译后的代码无法通过所有测试,但我认为代码应该是正确的,因为它只是使用暴力来解决问题。
- 有没有有效的方法来解决四和问题而不是这种 O(n^4) 运行时算法?
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
public class FourSumSolution{
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target){
ArrayList<ArrayList<Integer>> aList = new ArrayList<ArrayList<Integer>>();
int N = num.length;
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++)
for(int k=j+1; k<N; k++)
for(int l=k+1; l<N; l++){
int sum = num[i] + num[j] + num[k] + num[l];
if(sum == target){
ArrayList<Integer> tempArray = new ArrayList<Integer>();
Collections.addAll(tempArray, num[i], num[j], num[k], num[l]);
aList.add(tempArray);
}
}
return aList;
}
}
这是一个 O(n^3) 的解决方案
import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashSet;
public class Solution {
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
Arrays.sort(num);
HashSet<ArrayList<Integer>> hSet = new HashSet<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < num.length; i++) {
for (int j = i + 1; j < num.length; j++) {
for (int k = j + 1, l = num.length - 1; k < l;) {
int sum = num[i] + num[j] + num[k] + num[l];
if (sum > target) {
l--;
}
else if (sum < target) {
k++;
}
else if (sum == target) {
ArrayList<Integer> found = new ArrayList<Integer>();
found.add(num[i]);
found.add(num[j]);
found.add(num[k]);
found.add(num[l]);
if (!hSet.contains(found)) {
hSet.add(found);
result.add(found);
}
k++;
l--;
}
}
}
}
return result;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)