あなたのソリューションは明らかに正しく計算されています。ただし、値が入力配列に複数回出現する場合、「同じ」結果が得られます。多分それはテストされました。
target = 4 の num = { 1, 3, 1, 3, 4 } の "twoSum" は次のようになります。
- { 1, 3 }
- { 1, 3 }
- { 3, 1 }
- { 1, 3 }
これがテストで失敗した理由である場合、解決策はおそらく一連の順序付きリストになるでしょう。
サブセットも指定する必要がある場合は、{ 4 } がありません。
問題は、なぜテストが失敗したのか、要件は何かということです。
最適化には、おそらく特別なデータ構造が含まれます。少なくとも (逆に) ソートされた num です。多くのリンクがすでに与えられています。再帰は、事前条件と事後条件を使用して、証明可能で理解可能な最適解を見つけるのに役立ちます。（問題を分割しているため。）
1 つの解決策は、ペアの合計を、その合計につながるすべてのインデックスのペアにマッピングしたままペアを作成することです。次に、分離インデックスを持つ 2 つのペアを見つけます。
誰も満足のいく答えを出さなかったので：
単純な再帰的ソリューション (あまり良くない、または最適ではない)。ただし、データ構造が関連していることを示しています。
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) の最小値と候補用語の合計が大きすぎる場合は、候補用語をスキップします。
- 候補用語と次の (nTerm -1) 用語が小さすぎる場合は終了します。
- valuesCount < nTerms の場合は終了します