本文包含leetcode上的Two Sum（Python实现）、Two Sum II - Input array is sorted（Python实现）、Two Sum IV - Input is a BST（Java实现）三个类似的题目，现总结于此。
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].
问题描述：给定任意列表和目标值，输出和为目标值的2个元素的索引
方法一：双层循环（Python实现），最坏情况下，时间复杂度为O（N*N）
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
i1 = 0
flag = False
for num in nums:
num1 = target - num
i2 = i1+1;
for num2 in nums[i2:]:
if num1 == num2:
flag = True
break
else:
i2 += 1
if flag:
return [i1, i2]
i1 += 1
运行时间为：6308ms
方法二：空间换时间，采用字典存储所有结果，然后对列表进行遍历，空间复杂度为O(N)，最坏情况下，时间复杂度为O(N)
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) <= 1:
return False
num_dict = {}
for i in range(len(nums)):
num_dict[nums[i]] = i
for i in range(len(nums)):
subtractor = target - nums[i]
if subtractor in num_dict and i != num_dict[subtractor]:
return [i, num_dict[subtractor]]
运行时间：68ms
方法三：对方法二进一步优化，边存储边比较，最坏情况下时间复杂度为O(N)，空间复杂度为O(N)
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) <= 1:
return False
num_dict = {}
for i in range(len(nums)):
subtractor = target - nums[i]
if subtractor in num_dict:
return [num_dict[subtractor], i]
else:
num_dict[nums[i]] = i
运行时间：48ms
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.
问题描述：给定生序排列的列表和目标值，输出和为目标值的2个元素的位置
方法一：采用上一题的思路，利用字典存储已比较的值，最坏情况下时间复杂度为O(N)，空间复杂度为O(N)
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
if len(numbers) <= 1:
return False
num_dict = {}
for i in range(len(numbers)):
if numbers[i] in num_dict:
return [num_dict[numbers[i]]+1, i+1]
else:
num_dict[target - numbers[i]] = i
运行时间：64ms
方法二：方法一没有用上已排好序的条件，定义2个指针l和r，分别指向列表头和尾
- 如果2元素和正好等于目标值，则输出[ l+1，r+1]
- 如果和小于目标值，则l++
- 如果和大于目标值，则r--
最坏情况下，时间复杂度为O(N/2)。
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
if len(numbers) <= 1:
return False
l, r = 0, len(numbers)-1
while l < r:
s = numbers[l] + numbers[r]
if s == target:
return [l+1, r+1]
elif s < target:
l += 1
else:
r -= 1
运行时间：44ms
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）和目标值，判断是否存在2个节点元素和为目标值，若有则返回true，否则返回false。此题采用Java实现。
方法一：基于上边题目的经验，可以将该问题转换为上一题，即将BST中序遍历得到生序排列的列表，再采用l和r指针判断。
其中，中序遍历采用DFS，该方法时间复杂度为O(N)，空间复杂度为O(N)。
/**
* 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) {
List<Integer> list = new ArrayList<>();
t(root, list);
int l = 0;
int r = list.size()-1;
while(l < r){
int sum = list.get(l) + list.get(r);
if(sum == k){
return true;
} else if(sum < k){
l++;
} else{
r--;
}
}
return false;
}
private void t(TreeNode root, List<Integer> list){
TreeNode left = root.left;
TreeNode right = root.right;
if(left != null){
t(left, list);
}
list.add(root.val);
if(right != null){
t(right, list);
}
}
}
运行时间：17ms
方法二：看讨论区，说面试时可能更进一步，怎样实现空间复杂度为O(logN)。看到logN，应该想到可能需要用到BST的高度信息。
结合该题意思，核心在于查找target-num1的情况，即将问题转换为BST查找问题。最坏情况下，是需要遍历所有节点作为num1，然后在BST上找target-num1。
故可以结合DFS和BST二分查找，时间复杂度为O(nh)，空间复杂度为O(h)，其中h为书的高度，最好情况下为logN，最坏情况为N.
/**
* 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;
}
return dfs(root, root, k);
}
private boolean dfs(TreeNode root, TreeNode cur, int k){
if(cur == null){
return false;
}
//查两边情况，查左边和右边情况；由search方法作为算法的查找；后边进行递归左右分支
return search(root, cur, k-cur.val) || dfs(root, cur.left, k) || dfs(root, cur.right, k);
}
//二叉查找树 查某数，时间复杂度为 O(h),空间复杂度为O(h)
private boolean search(TreeNode root, TreeNode cur, int value){
if(root == null){
return false;
}
if(root.val == value && root != cur){
return true;
} else if(root.val < value){
return search(root.right, cur, value);
} else if(root.val > value){
return search(root.left, cur, value);
}
return false;
}
}
运行时间：24ms
可参考：https://leetcode.com/problems/two-sum-iv-input-is-a-bst/discuss/106059/JavaC++-Three-simple-methods-choose-one-you-like（方法一对应参考method2，方法二对应参考method3）
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/（方法一对应method3，method1和method2分别用DFS和BFS实现遍历）