原題：
給定一個(gè)數(shù)組candidate和一個(gè)目標(biāo)值target,求出candidate中兩個(gè)數(shù)的和等于target的組合。比如輸入數(shù)組[1,2,3,4,7]和目標(biāo)值10.輸出[ 3, 7]如果找不到輸出[ -1,-1 ]。要求時(shí)間復(fù)雜度盡量是O(n)。
思路：
求兩個(gè)數(shù)字之和，假設(shè)給定的和為target。一個(gè)變通的思路，就是對(duì)數(shù)組中的每個(gè)數(shù)字arr[i]都判別target-arr[i]是否在數(shù)組中，這樣，就變通成為一個(gè)查找的算法。
在一個(gè)無(wú)序數(shù)組中查找一個(gè)數(shù)的復(fù)雜度是O（N），對(duì)于每個(gè)數(shù)字arr[i]，都需要查找對(duì)應(yīng)的target-arr[i]在不在數(shù)組中，很容易得到時(shí)間復(fù)雜度還是O（N^2）。這和最原始的方法相比沒(méi)有改進(jìn)。但是如果能夠提高查找的效率，就能夠提高整個(gè)算法的效率。怎樣提高查找的效率呢？
學(xué)過(guò)編程的人都知道，提高查找效率通常可以先將要查找的數(shù)組排序，然后用二分查找等方法進(jìn)行查找，就可以將原來(lái)O（N）的查找時(shí)間縮短到O（log2N），這樣對(duì)于每個(gè)arr[i]，都要花O（log2N）去查找對(duì)應(yīng)的target-arr[i]在不在數(shù)組中，總的時(shí)間復(fù)雜度降低為N* log2N。當(dāng)讓將長(zhǎng)度為N的數(shù)組進(jìn)行排序本身也需要O（Nlog2N）的時(shí)間，好在只須要排序一次就夠了，所以總的時(shí)間復(fù)雜度依然O（Nlog2N）。這樣，就改進(jìn)了最原始的方法。
到這里，有的讀者可能會(huì)更進(jìn)一步地想，先排序再二分查找固然可以將時(shí)間從O（N^2）縮短到O（N*log2N），但是還有更快的查找方法：hash表。因?yàn)榻o定一個(gè)數(shù)字，根據(jù)hash表映射查找另一個(gè)數(shù)字是否在數(shù)組中，只需要O（1）時(shí)間。這樣的話，總體的算法復(fù)雜度可以降低到O（N），但這種方法需要額外增加O（N）的hash表存儲(chǔ)空間。某些情況下，用空間換時(shí)間也不失為一個(gè)好方法。
算法如下：
public static String findSumtwo(int [] candidates, int target){
if(candidates==null||candidates.length<2){
return null;
}
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<candidates.length;i++){
map.put(i,array[i]);
}
int [] failOut=new int[]{-1,-1};
for(int j=0;j<candidates.length;j++){
if(map.containsValue(target-candidates[j])&& map.get(target-candidates[j])!=j){
int [] t=new int[2];
t[0]=array[j];
t[1]=target-candidates[j];
return Arrays.toString(t);
}
}
return Arrays.toString(failOut);
}
那么問(wèn)題來(lái)了，如果輸出所有組合，不限于兩個(gè)數(shù)的組合呢？
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8。
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
思路一樣，代碼如下：
public class Solution {
public List<List<Integer>>combinationSum2(int[] candidates, int target) {
List<List<Integer>> mList = null;
if(candidates == null || candidates.length < 1)
return mList;
Arrays.sort(candidates);
List<Integer> list = new ArrayList<Integer>();
Set<List<Integer>> set = new HashSet<List<Integer>>(); // List和set,其實(shí)是一樣的，因?yàn)橹皩?duì)數(shù)組排過(guò)序了
combinationCore(candidates, 0, target, list , set );
mList = new ArrayList<>(set);
return mList ;
}
public void combinationCore(int[] candidates, int index, int target, List<Integer> list, Set<List<Integer>> set){
for(int i = index; i < candidates.length; i++){
if(target == candidates[i]){
List<Integer> res = new ArrayList<Integer>();
res.addAll(list);
res.add(candidates[i]);
set.add(res);
}
else if(target > candidates[i]){
List<Integer> res = new ArrayList<Integer>();
res.addAll(list);
res.add(candidates[i]);
combinationCore(candidates, i + 1, target - candidates[i], res, set); // 注意這里是i + 1
}
else
break;
}
}
}
