原題：
給定一個數(shù)組candidate和一個目標值target,求出candidate中兩個數(shù)的和等于target的組合悟衩。比如輸入數(shù)組[1,2,3,4,7]和目標值10.輸出[ 3, 7]如果找不到輸出[ -1,-1 ]娘赴。要求時間復雜度盡量是O(n)。
思路：
求兩個數(shù)字之和郑藏，假設給定的和為target。一個變通的思路，就是對數(shù)組中的每個數(shù)字arr[i]都判別target-arr[i]是否在數(shù)組中贿堰，這樣跑杭，就變通成為一個查找的算法铆帽。
在一個無序數(shù)組中查找一個數(shù)的復雜度是O（N），對于每個數(shù)字arr[i]德谅，都需要查找對應的target-arr[i]在不在數(shù)組中爹橱，很容易得到時間復雜度還是O（N^2）。這和最原始的方法相比沒有改進窄做。但是如果能夠提高查找的效率愧驱，就能夠提高整個算法的效率。怎樣提高查找的效率呢椭盏？
學過編程的人都知道组砚，提高查找效率通常可以先將要查找的數(shù)組排序掏颊，然后用二分查找等方法進行查找糟红，就可以將原來O（N）的查找時間縮短到O（log2N）艾帐，這樣對于每個arr[i]，都要花O（log2N）去查找對應的target-arr[i]在不在數(shù)組中盆偿，總的時間復雜度降低為N* log2N柒爸。當讓將長度為N的數(shù)組進行排序本身也需要O（Nlog2N）的時間，好在只須要排序一次就夠了事扭，所以總的時間復雜度依然O（Nlog2N）捎稚。這樣，就改進了最原始的方法求橄。
到這里今野，有的讀者可能會更進一步地想，先排序再二分查找固然可以將時間從O（N^2）縮短到O（N*log2N）罐农，但是還有更快的查找方法：hash表条霜。因為給定一個數(shù)字，根據(jù)hash表映射查找另一個數(shù)字是否在數(shù)組中啃匿，只需要O（1）時間蛔外。這樣的話，總體的算法復雜度可以降低到O（N）溯乒，但這種方法需要額外增加O（N）的hash表存儲空間夹厌。某些情況下，用空間換時間也不失為一個好方法裆悄。
算法如下：
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);
}
那么問題來了矛纹，如果輸出所有組合，不限于兩個數(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ù)組排過序了
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;
}
}
}
