Two Sum I & II
Two Sum I
Given an array of integers, 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.
You may assume that each input would have exactly one solution
numbers=[2, 7, 11, 15], target=9
return [0, 1]
分析：
利用hashMap把值和对应的Index放在里面。然后对于剩余的值，在hashmap里查找就可以了。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[];
HashMap<Integer,Integer> map = new HashMap<>();
for (int i = ; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[] = map.get(target - numbers[i]);
result[] = i;
return result;
}
map.put(numbers[i], i);
}
return result;
}
}
扩展：如果里面不止一对，需要找出所有的，并且数组中的数还可能有重复，这种情况也是同样的处理方法，只是把map中的值变成ArrayList就可以了。
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 sameelement twice.
class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == ) {
return null;
}
int i = ;
int j = numbers.length - ;
while (i < j) {
int sum = numbers[i] + numbers[j];
if (sum < target) {
++i;
} else if (sum > target) {
j--;
} else {
return new int[] { i + , j + };
}
}
return null;
}
}
Two Sum III
Design and implement a TwoSum class. It should support the following operations: add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1);
add(3);
add(5);
find(4) -> true
find(7) -> false
public class TwoSum {
HashMap<Integer, Integer> map;
public TwoSum() {
map = new HashMap<Integer, Integer>();
}
public void add(int x) {
map.put(x, map.getOrDefault(x, ) + );
}
public boolean find(int target) {
for (int i : map.keySet()) {
if (map.containsKey(target - i)) {
if (target - i != i || map.get(i) >= )
return true;
}
}
return false;
}
}
If find method is called very frequently, we should use the implementation below.
public class TwoSum {
private Set<Integer> sum, num;
public TwoSum() {
sum = new HashSet<Integer>();
num = new HashSet<Integer>();
}
// Add the number to an internal data structure.
public void add(int number) {
if (num.contains(number)) {
sum.add(number * );
} else {
Iterator<Integer> iter = num.iterator();
while (iter.hasNext()) {
sum.add(iter.next() + number);
}
num.add(number);
}
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
return sum.contains(value);
}
}
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
方法一：先把bst转化成一个sorted arraylist, 然后用上一题的方法即可。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
List<Integer> list = new ArrayList();
inorder(root, list);
int i = ;
int j = list.size() - ; while (j > i) {
long sum = list.get(i) + list.get(j);
if (sum == k) {
return true;
} else if (sum > k) {
j--;
} else {
i++;
}
}
return false;
} private void inorder(TreeNode root, List<Integer> list) {
if (root == null) {
return;
}
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
}
}
方法二：利用递归+ hashset. 这个方法有点意思，所以记录下来。
class Solution {
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
Set<Integer> numbers = new HashSet();
return dfs(root, numbers, k);
}
private boolean dfs(TreeNode root, Set<Integer> numbers, int k) {
if (root == null) {
return false;
}
if (numbers.contains(k - root.val)) {
return true;
}
numbers.add(root.val);
return dfs(root.left, numbers, k) || dfs(root.right, numbers, k);
}
}
最新文章
- Spring--开山篇
- 用Visual Studio 2012+Xamarin搭建C#开发Andriod的环境
- CODESOFT 2015中的条形码对象该如何创建
- ADO.NET基本操作（CRUD、Procedure、Transaction）
- [一]初识JFreeChart
- Drawable、Bitmap、byte[]之间的转换
- Jsp内置对象-session
- 设置JQuery的Ajax方法同步
- JS排序算法
- 利用shell脚本实现对mysql数据库的备份
- 软工网络15个人作业4——alpha阶段个人总结
- ---- 关于Android蓝牙搜索到设备的图标显示和设备过滤
- jhipster安装_Windows
- mysql常用命令行操作(一)：登陆、退出、查看端口、修改密码、刷新
- IdentityServer4【Topic】之定义客户端
- Delphi2009之TImage
- Nginx使用Location匹配URL进行伪静态
- 原生js（一）
- Spring Boot系列教程六：日志输出配置log4j2
- rsync--数据镜像备份_转