给定整数集合和目标值找出集合中和为目标值的元素

1.给定的数组没有排序

给定一个整型数组array和一个整数target，在数组中找出两个整数相加之和为target，返回这两个整数的下标。

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

1.1 双层for循环

最容易想到的方法就是使用两层for循环去遍历，但是这种方法时间复杂度为O(n^2)

public int[] twoSum(int[] array, int target) {
        int[] result  = new int[2];
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] + array[j] == target) {
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
  }

1.2 使用HashMap

一种较为优化的解法是使用HashMap，key为当前整型数num，value为下标index，判断target-num是否在当前HashMap中，若在则返回num的下标同时从HashMap中取出target-num的下标，否则将num放入HashMap。

public int[] twoSum(int[] array,int target){
    HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i = 0;i<array.length;i++){
        int tmp = target-array[i];
        if(map.containsKey(tmp)){
            return new int[]{i,map.get(tmp)};
        }else{
            map.put(array[i],i);
        }
    }
    throw new IllegalArgumentException("not find two num");
}

2.给定的数组已排序

还是上面的数组，但是这次的条件是数组已经排序。总体来说排序以后整个难度会降低。其思路就是使用两个指针从数组的头尾分别移动，如果拿到的两个数之和大于目标值，则说明尾指针需要向前移动，否则头指针需要向后移动。
代码如下：

 public int[] twoSum(int []array,int target){
        int i = 0;
        int j = array.length-1;
        while(i<j){
            int sum = array[i] + array[j];
            if(sum>target){
                j --;
            }else if(sum < target){
                i ++;
            }else{
                return new int[]{i,j};
            }
        }

        throw new IllegalArgumentException("not find two num");
    }

有了上面的解题思路，针对未排序的数组，一种思路就是先排序再求解。第一步使用快排等排序算法能将时间复杂度控制在O(NlogN)，然后使用上面的方式，总的时间复杂度为O(nlogn)+O(n)。比上面使用第一种方式的O(n^2)要好。

3.给定的数组换成二叉搜索树

上面的数组换成二叉搜索树（BST），判断此树中是否有两个数，使得这两个数的加和为target。BST的定义如下：

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;
}

3.1 中序遍历BST

BST中序遍历的结果是一个升序排序的集合，所以这种解法就是先中序遍历BST，然后使用排序数组的解法。

 public boolean findTarget(TreeNode root, int k) {
        List<Integer> nodes = new ArrayList<Integer>();
        inorder(root,nodes);
        int i = 0;
        int j = nodes.size()-1;
        while (i<j){
            int sum = nodes.get(i)+nodes.get(j);
            if(sum>k){
                j--;
            }else if(sum<k){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }

    void inorder(TreeNode root, List<Integer> nodes){
        if(root !=null){
            inorder(root.left,nodes);
            nodes.add(root.val);
            inorder(root.right,nodes);
        }
    }

第一遍提交的时候脑子抽了，把遍历二叉树存入List的代码写成了下面这样, 返回的集合里面只有根节点的元素，果断运行不通过。

 List<Integer> inorder(TreeNode root){
    List<Integer> nodes = new ArrayList<Integer>();
    if(root!=null){
        inorder(root.left);
        nodes.add(root.value);
        inorder(root.right);
    }

    return nodes;
 }

3.2 从根节点遍历BST

从根节点开始遍历BST，将节点的的value值存入HashSet，如果后续遍历中遇到节点n，target-n.value在HashSet中，则说明有满足条件的两个值，代码如下

    public boolean findTarget(TreeNode root, int k) {
         HashSet<Integer> num = new HashSet<Integer>();
        return find(root,k,num);
    }

    public boolean find(TreeNode root,int target,HashSet<Integer> num){
        if(root == null){
            return false;
        }
        if(num.contains(target - root.val)){
            return true;
        }
        num.add(root.val);
        return find(root.left,target,num) || find(root.right,target,num);
    }

3.3 广度优先遍历二叉树（BSF）

一种比较好容易理解的方式是使用广度优先遍历二叉树，类似于上一种方式，将节点的值存入HashSet，在遍历过程中判断target-node.value是否存在。

public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> num = new HashSet<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.remove();
            if(num.contains(k-node.val)){
                return true;
            }
            num.add(node.val);
            if(node.left !=null){
                queue.offer(node.left);
            }
           if(node.right !=null){
               queue.offer(node.right);
           }
        }
        return false;
    }

4. 从数组中找出三个元素之和为n

给定一个数组，从数组中找出所有的a,b,c使得a+b+c之和为0，且所有的解不能重复。比如[-1,0,1]和[-1,1,0]算作重复的。
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路：
threesum问题分解成twosum问题，让其中一个加数a固定的从数组第一个往数组倒数第三个滑动（不能移动到尾部，因为还有两个加数）。此时twosum问题的target就是0-a。然后解决twosum问题就行，但是难点在于如何对不同的解去重。刚开始想的思路是将一组解合并成一个字符串，放到HashSet来去重。去重目的是达到了，但是将HashSet转成题目需要的List又要一层for循环，在跑最后一个变态case的时候超时。代码如下：

 public List<List<Integer>> threeSum(int[] nums) {
          Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        HashSet<String> sets = new HashSet<String>();
        for(int i = 0;i<nums.length-2;i++){
            int tmp = 0 - nums[i];
            int start = i+1;
            int end = nums.length-1;
           while(start<end){
               int twosum = nums[start]+nums[end];
               if(twosum<tmp){
                   start ++;
               }else if(twosum>tmp){
                   end --;
               }else{
                   sets.add(nums[i]+"#"+nums[start]+"#"+nums[end]);
                   start++;
               }
           }
        }

        for(String str:sets){
            String parts[] = str.split("#");
            res.add(Arrays.asList(Integer.parseInt(parts[0]),Integer.parseInt(parts[1]),Integer.parseInt(parts[2])));
        }
        return res;
     }

后来看了讨论区大神写的代码，果然精简高效，贴出来膜拜。

public List<List<Integer>> threeSum(int[] num) {
    Arrays.sort(num);
    List<List<Integer>> res = new LinkedList<>(); 
    for (int i = 0; i < num.length-2; i++) {
        if (i == 0 || (i > 0 && num[i] != num[i-1])) {
            int lo = i+1, hi = num.length-1, sum = 0 - num[i];
            while (lo < hi) {
                if (num[lo] + num[hi] == sum) {
                    res.add(Arrays.asList(num[i], num[lo], num[hi]));
                    while (lo < hi && num[lo] == num[lo+1]) lo++;
                    while (lo < hi && num[hi] == num[hi-1]) hi--;
                    lo++; hi--;
                } else if (num[lo] + num[hi] < sum) lo++;
                else hi--;
           }
        }
    }
    return res;
}