数组中找到2，3，n个数等于一个值

1、给定一个数组，找到数组中两个元素等于一个值。

1.1、先排序，两个指针，一个指头一个指尾，遍历一遍即可找到，时间复杂度为O(nlgn)（排序的时间），空间复杂度为O(1)。

1.2、利用hashmap存放当前元素对应的元素，遍历一次就可找到，时间复杂度为O(n)，空间复杂度为O(n)。

public static int[] getTwoSum(int []val,int target){
        HashMap<Integer,Integer> map=new HashMap<Integer, Integer>();
int result[]=new int[2];
for(int i=0;i<val.length;i++){
if(map.containsKey(val[i])){
                result[0]=map.get(val[i]);
                result[1]=i;
break;
            }else{
map.put(target-val[i], i);
            }
        }
return result;
    }

2、给定一个数组，找到三个值等于一个数

2.1、直接回溯，时间复杂度为O（2^n），通过截支法可以去掉一大部分，但是仍然太慢。

2.2、先将数组排序，固定开头，然后用两个指针标记遍历的头尾，如果开头+头+尾的和等于target，放入list中，头指针+1，尾指针-1；如果小于target，头指针+1；如果大于target，尾指针-1。时间复杂度为O(n^2)。

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0; i < nums.length-2; i++) {
if(i > 0 && (nums[i] == nums[i-1])) continue; // delete duplicate 
for(int j = i+1, k = nums.length-1; j<k;) {
if(nums[i] + nums[j] + nums[k] == 0) {
list.add(Arrays.asList(nums[i],nums[j],nums[k]));
                j++;k--;
while((j < k) && (nums[j] == nums[j-1]))j++;// delete duplicate 
while((j < k) && (nums[k] == nums[k+1]))k--;// delete duplicate 
            }else if(nums[i] + nums[j] + nums[k] > 0) k--;
else j++;
        }
    }
return list;
}

3、数组中找到n个数等于一个值，没有重复。例如A=10,1,2,7,6,1,5 target=8，求出的结果是：[1, 7] ，[1, 2, 5] ，[2, 6] ，[1, 1, 6] 。

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> ans=new ArrayList<List<Integer>>();    
    ch(candidates,target,0,new ArrayList<Integer>(),ans);
return ans;
}
public void ch(int[] candidates,int remain,int rindex,List<Integer> tmp,List<List<Integer>> ans)
{
if(remain==0)
    {
        List<Integer> a=new ArrayList<Integer>(tmp);
        ans.add(a);
return;
    }
int entered=0; // get rid of duplicate combinations
for(int i=rindex;i<candidates.length;i++)
    {
if(entered!=candidates[i]) // get rid of duplicate combinations
        {
if(remain-candidates[i]<0) break; //This line of code can reduce 7ms from execution time!
            tmp.add(candidates[i]);
            entered=candidates[i];
            ch(candidates,remain-candidates[i],i+1,tmp,ans);
            tmp.remove(tmp.size()-1); 
        }   
    }
}