目录
? ? ? 各位小伙伴，欢迎大家和我一同步入算法专栏；在接下来的篇章中，我会详细讲述，总结自己在刷算法题中的一些技巧和方法，提高自己的算法能力，希望感兴趣的小伙伴能和我一起学习，共同进步???
题目一：两数之和Ⅰ
给定一个整数数组 nums?和一个整数目标值 target，请你在该数组中找出 和为目标值 target??的那?两个?整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
题目链接：LeetCode
示例：
输入：nums = [2,7,11,15], target = 13
输出：[0,2]
解释：因为 nums[0] + nums[2] == 13?，返回 [0, 2] 。
解题思路：当看到这道题的时候，我最开始的思路是先确定一个元素 nums[i] ,nums[j],（j = i + 1),然后通过循环去遍历整个数组，查找是否存在 nums[i]? + nums[j] == target;这样通过枚举的方法，它的时间复杂度是?O(N^2)，空间复杂度是 O(1)。刚好最近学习了哈希表，我又想到快速寻找数组中是否存在目标元素的方法，这样就可以大大简化算法的时间复杂度了。
方法一：暴力枚举
public Solution {
public int[] twoSum(int[] nums,int target){
for(int i = 0;i < nums.length;i++){
for(int j = i + 1;j < nums.length;j++){
if(nums[i] + nums[j] == target){
return new int[] {i,j};
}
}
}
return new int[0];
}
}方法二：哈希表
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
题目二：两数之和Ⅱ - 输入有序数组
给你一个下标从 1 开始的整数数组?numbers ，该数组已按 非递减顺序排列??，请你从数组中找出满足相加之和等于目标数?target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
题目链接：LeetCode
示例：
输入：nums = [2,7,11,15], target = 9
输出：[1，2]
解释：因为 nums[1] + nums[2] == 9 ，返回 [1，2] 。
解题思路：这道题也可以使用题目一中的两个方法，但是这两种解法都是针对无序数组的，没有利用到输入数组有序的性质。利用输入数组有序的性质，可以得到时间复杂度和空间复杂度更优的解法。
方法一：二分查找
在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。
class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; ++i) {
int low = i + 1, high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
return new int[]{i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return new int[]{0,0};
}
}方法二：双指针
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位。如果两个元素之和大于目标值，则将右侧指针左移一位。移动指针之后，重复上述操作，直到找到答案。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int low = 0, high = numbers.length - 1;
while (low < high) {
int sum = numbers[low] + numbers[high];
if (sum == target) {
return new int[]{low + 1, high + 1};
} else if (sum < target) {
++low;
} else {
--high;
}
}
return new int[]{-1, -1};
}
}题目三：两数之和Ⅲ - 数据结构设计
设计并实现一个 TwoSum 的类，使该类需要支持 add 和 find 的操作。
add 操作 - 对内部数据结构增加一个数。
find 操作 - 寻找内部数据结构中是否存在一对整数，使得两数之和与给定的数相等。题目链接：LeetCode
示例：
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
解题思路：twoSum题的拓展，设计一个数据结构，实现添加数字和找目标数字的功能。用 HashMap 来存数字和查找。
代码示例
public class TwoSum {
private HashMap<Integer, Integer> elements = new HashMap<Integer, Integer>();
public void add(int number) {
if (elements.containsKey(number)) {
elements.put(number, elements.get(number) + 1);
} else {
elements.put(number, 1);
}
}
public boolean find(int value) {
for (Integer i : elements.keySet()) {
int target = value - i;
if (elements.containsKey(target)) {
if (i == target && elements.get(target) < 2) {
continue;
}
return true;
}
}
return false;
}
}题目四：两数之和Ⅳ - 输入BST
给定一个二叉搜索树?
root?和一个目标结果?k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回?true。题目链接：LeetCode
示例:
输入：root = [7，5，8，4，6，null，9]，k = 13
输出：true
输入：root = [7，5，8，4，6，null，9]，k = 30
输出：false
解题思路：我们可以使用深度优先搜索的方式遍历整棵树，用哈希表记录遍历过的节点的值。对于一个值为 xx 的节点，我们检查哈希表中是否存在 k - xk?x 即可。如果存在对应的元素，那么我们就可以在该树上找到两个节点的和为 kk；否则，我们将 xx 放入到哈希表中。如果遍历完整棵树都不存在对应的元素，那么该树上不存在两个和为 kk 的节点。
代码示例
class Solution {
Set<Integer> set = new HashSet<Integer>();
public boolean findTarget(TreeNode root, int k) {
if (root == null) {
return false;
}
if (set.contains(k - root.val)) {
return true;
}
set.add(root.val);
return findTarget(root.left, k) || findTarget(root.right, k);
}
}