您的解决方案显然计算正确。但是，如果一个值在输入数组中出现多次，则会给出“相同”的结果。也许那是经过测试的。
num = { 1, 3, 1, 3, 4 } 与 target = 4 的“twoSum”将是：
- { 1, 3 }
- { 1, 3 }
- { 3, 1 }
- { 1, 3 }
这是测试失败的原因，解决方案可能是一组有序列表。
如果还必须给出子集，则缺少 { 4 }。
所以问题是，为什么测试失败了，有什么要求。
优化可能涉及特殊的数据结构：至少一个（反向）排序的 num。许多链接已经给出。递归可以帮助找到一个可证明和可理解的最优解，包括前置条件和后置条件。（当您拆分问题时。）
一种解决方案是创建对，保持对总和到导致该总和的所有索引对的映射。然后找到两对具有分离索引的对。
由于没有人给出满意的答案：
一个简单的递归解决方案（不是很好或最优）。然而，它表明数据结构是相关的。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.SortedSet;
import java.util.TreeSet;
public class FourSumSolution {
private static class SortedTuple implements Comparable<SortedTuple> {
int[] values;
public SortedTuple(int... values) {
this.values = Arrays.copyOf(values, values.length);
Arrays.sort(this.values);
}
public int size() {
return values.length;
}
public int get(int index) {
return values[index];
}
public ArrayList<Integer> asList() {
// Result type is ArrayList and not the better List,
// because of the external API of the outer class.
ArrayList<Integer> list = new ArrayList<Integer>(values.length);
for (int value: values)
list.add(value);
return list;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + Arrays.hashCode(values);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
SortedTuple other = (SortedTuple) obj;
if (!Arrays.equals(values, other.values))
return false;
return true;
}
@Override
public int compareTo(SortedTuple other) {
int c = cmp(values.length, other.values.length);
if (c == 0) {
for (int i = 0; i < values.length; ++i) {
c = cmp(values[i], other.values[i]);
if (c != 0)
break;
}
}
return c;
}
@Override
public String toString() {
return Arrays.toString(values);
}
private static int cmp(int lhs, int rhs) {
return lhs < rhs ? -1 : lhs > rhs ? 1 : 0; // Cannot overflow like lhs - rhs.
}
}
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
final int nTerms = 4;
SortedTuple values = new SortedTuple(num);
SortedSet<SortedTuple> results = new TreeSet<SortedTuple>();
int[] candidateTerms = new int[nTerms];
int valuesCount = values.size();
solveNSum(target, nTerms, values, results, candidateTerms, valuesCount);
ArrayList<ArrayList<Integer>> aList = new ArrayList<ArrayList<Integer>>();
for (SortedTuple solution: results) {
aList.add(solution.asList());
}
return aList;
}
public static void main(String[] args) {
final int[] num = { 1, 3, 1, 3, 4 };
final int requiredSum = 4;
final int nTerms = 2;
SortedTuple values = new SortedTuple(num);
SortedSet<SortedTuple> results = new TreeSet<SortedTuple>();
int[] candidateTerms = new int[nTerms];
int valuesCount = values.size();
solveNSum(requiredSum, nTerms, values, results, candidateTerms, valuesCount);
System.out.println("Solutions:");
for (SortedTuple solution: results) {
System.out.println("Solution: " + solution);
}
System.out.println("End of solutions.");
}
private static void solveNSum(int requiredSum, int nTerms, SortedTuple values, SortedSet<SortedTuple> results, int[] candidateTerms, int valuesCount) {
if (nTerms <= 0) {
if (requiredSum == 0)
results.add(new SortedTuple(candidateTerms));
return;
}
if (valuesCount <= 0) {
return;
}
--valuesCount;
int candidateTerm = values.get(valuesCount);
// Try with candidate term:
candidateTerms[nTerms - 1] = candidateTerm;
solveNSum(requiredSum - candidateTerm, nTerms - 1, values, results, candidateTerms, valuesCount);
// Try without candidate term:
solveNSum(requiredSum, nTerms, values, results, candidateTerms, valuesCount);
}
}
可以进一步修剪：
- 如果 (nTerms - 1) 最低加上候选词给出的总和太大，则跳过候选词；
- 如果候选词加上下一个 (nTerms -1) 词太小，则终止。
- 如果 valuesCount < nTerms 则终止