【LeetCode】Two Sum问题
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);
}
}
还没有评论,来说两句吧...