某公司的笔试编程题

原题：

给定一个数组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;
    }
   }
 }

博客园：http://www.cnblogs.com/leavescy/p/5901338.html