Two Sum问题合集

Description

Two Sum 问题合集

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Solution

[leetcode 1]Two Sum

这种题目一般需要限制时间复杂度或者空间复杂度，给出一个比较常用的解法吧，时间复杂度为O(n)，空间复杂度为O(n)。思路就是对数组中的每个元素遍历，并将其存储到Map的key中，value是下标，我们的目的是找出两个元素a和b，使得a+b=target，也就是说对于当前遍历的元素a，如果在Map中存在一个元素b（为之前遍历的元素），使得target-a等于b，那么我们的目的就达到了，return即可。

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

当然了，我觉得还是先排序，然后再遍历，这样空间复杂度为O(1)，虽然排序的时间复杂度为O(nlgn)，下面这道题就是这样。

[leetcode 167] Two Sum II - Input array is sorted

给定一个排序的数组，然后假定没有重复元素，只有一个解，返回元素的下标(从1计算)，那就好办了，不用Map了。思路是用两个指针(start，end)分别指向数组的头和尾，比较start所指的元素和end所指的元素之和是否等于target，如果等于，直接返回下标即可；如果大于，说明需要更小的元素来匹配，那么将end指针向左移即可；如果小于，说明需要更大的元素来匹配，将start指针向右移动即可，跳出条件的start>=end，代码如下：

public int[] twoSum(int[] numbers, int target) {
    int [] res=new int[2];
    int start,end;
    start=0;
    end=numbers.length-1;
    while (start<end){
        int temp=numbers[start]+numbers[end];
        if(temp==target){
            res[0]=start+1;
            res[1]=end+1;
            return res;
        }else if(temp>target)end--;
        else start++;
    }
    return res;
}

当然Two Sum还有很多玩法，可以放到二叉搜索树中，如下一题所示，不过原理不变，就上面两种。

[leetcode 653]Two Sum IV - Input is a BST

对于一棵二叉搜索树，给定一个target，是否存在两个节点的和等于target？
第一种方法是第一道题用到的，可以用在任何场合，即使用DFS遍历树，使用Set存储节点（这里只用判断是否存在，而不用返回节点，所以不需要Map），对于遍历的节点node，判断target-node.val是否在Set中。时间复杂度和空间复杂度都是O(n)，代码如下：

public boolean findTarget(TreeNode root, int k) {
    HashSet<Integer> set = new HashSet<>();
    return dfs(root, set, k);
}
public boolean dfs(TreeNode root, HashSet<Integer> set, int k){
    if(root == null)return false;
    if(set.contains(k - root.val))return true;
    set.add(root.val);
    return dfs(root.left, set, k) || dfs(root.right, set, k);
}

第二种方法就是上面第二道题用到的，需要一个排好序的数组，我们知道二叉搜索树的前序遍历的结果就是一个排好序的序列，那么先排序，然后遍历即可，代码如下：

public boolean findTarget(TreeNode root, int k) {
    List<Integer> nums = new ArrayList<>();
    inorder(root, nums);
    for(int i = 0, j = nums.size()-1; i<j;){
        if(nums.get(i) + nums.get(j) == k)return true;
        if(nums.get(i) + nums.get(j) < k)i++;
        else j--;
    }
    return false;
}
public void inorder(TreeNode root, List<Integer> nums){
    if(root == null)return;
    inorder(root.left, nums);
    nums.add(root.val);
    inorder(root.right, nums);
}

参考：Three simple methods - choose one you like