【LeetCode】Two Sum问题

迈不过友情╰ 2022-05-26 09:48 168阅读 0赞

> 1.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\].

> 思路：

数组无序，我们遍历数组时，判断其与target的差值，如果差值在数组中，并且不是自身，那么就是符合条件的，返回两个值的索引位置就可以；我们判断差值是否在数组中，并且如果存在快速定位，通过hashmap实现

class Solution {
        public int[] twoSum(int[] nums, int target) {
            if(nums == null || nums.length == 0)
                return null;
            HashMap<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<nums.length;i++){
                //计算差值
                int diff = target-nums[i];
                //如果包含，则返回差值的索引位置+当前元素的索引位置
                if(map.containsKey(diff)){
                    return new int[]{map.get(diff),i};
                }
                //不包含的话，将元素放入map中
                map.put(nums[i],i);
            }
            return null;
        }
    }

> 167.Two Sum II - Input array is sorted

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.

Note:

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.  
**Example:**  
Input: numbers = \[2, 7, 11, 15\], target = 9  
Output: \[1,2\]  
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

> 思路：

给定有序的数组，找出其中两个元素的和为目标值。  
很简单，两个变量，一个指向数组尾部，一个指向数组头部，如果相加为目标值，返回起始+1；如果小于，则将begin后移；如果大于，则将end前移；如果begin

class Solution {
        public int[] twoSum(int[] numbers, int target) {
            if(numbers == null || numbers.length == 0)
                return null;
            int begin = 0;
            int end = numbers.length-1;
            while(begin < end){
                if(target == numbers[begin]+numbers[end])
                    return new int[]{
       begin+1,end+1};
                else if(target < numbers[begin]+numbers[end])
                    end--;
                else
                    begin++;
            }
            return null;
        }
    }

> 653.Two Sum IV - Input is a BST

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.

Example 1:  
Input:  
5  
/ \\  
3 6  
/ \\ \\  
2 4 7

Target = 9

Output: True  
Example 2:  
Input:  
              5  
            /     \\  
          3       6  
          /   \\       \\  
        2     4       7

Target = 28

Output: False

> 思路：

求得二叉搜索树中两个树节点的值为目标值  
对于遍历过的结点，应该保存下来，在hashSet中，以便于在进行深度遍历DFS的时候将目前遍历的结点与目标值的差值是否在hashSet中，如果存在，就返回false，否则将当前结点加入hashSet中，继续递归遍历该结点的左右子树

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    import java.util.*;
    class Solution {
        Set<Integer> set = new HashSet<>();
        public boolean findTarget(TreeNode root, int k) {
            if(root == null)
                return false;
            if(set.contains(k - root.val))
                return true;
            else
                set.add(root.val);
            return findTarget(root.left,k)||findTarget(root.right,k);
        }
    
    }