某公司的笔试编程题
2016-09-26 本文已影响170人
装置图
原题：
给定一个数组candidate和一个目标值target,求出candidate中两个数的和等于target的组合。比如输入数组[1,2,3,4,7]和目标值10.输出[ 3, 7]如果找不到输出[ -1,-1 ]。要求时间复杂度尽量是O(n)。
思路：
求两个数字之和，假设给定的和为target。一个变通的思路，就是对数组中的每个数字arr[i]都判别target-arr[i]是否在数组中，这样，就变通成为一个查找的算法。
在一个无序数组中查找一个数的复杂度是O（N），对于每个数字arr[i]，都需要查找对应的target-arr[i]在不在数组中，很容易得到时间复杂度还是O（N^2）。这和最原始的方法相比没有改进。但是如果能够提高查找的效率，就能够提高整个算法的效率。怎样提高查找的效率呢？
学过编程的人都知道，提高查找效率通常可以先将要查找的数组排序，然后用二分查找等方法进行查找，就可以将原来O（N）的查找时间缩短到O（log2N），这样对于每个arr[i]，都要花O（log2N）去查找对应的target-arr[i]在不在数组中，总的时间复杂度降低为N* log2N。当让将长度为N的数组进行排序本身也需要O（Nlog2N）的时间，好在只须要排序一次就够了，所以总的时间复杂度依然O（Nlog2N）。这样，就改进了最原始的方法。
到这里，有的读者可能会更进一步地想，先排序再二分查找固然可以将时间从O（N^2）缩短到O（N*log2N），但是还有更快的查找方法：hash表。因为给定一个数字，根据hash表映射查找另一个数字是否在数组中，只需要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);
}
那么问题来了，如果输出所有组合，不限于两个数的组合呢？
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,其实是一样的，因为之前对数组排过序了
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;
}
}
}
