简单题：
1. 两数之和
167. 两数之和 II - 输入有序数组
653. 两数之和 IV - 输入 BST
中等题：
15. 三数之和
16. 最接近的三数之和
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/two-sum/">1. 两数之和</a></h3>
<h4>解法</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for index, value in enumerate(nums):
res = target - value
if(res in hashmap):
return(hashmap[res],index)
hashmap[value]=index
# Method 2
# for i in range(len(nums)):
# j = len(nums) - 1
# while(j > i):
# if(nums[i] + nums[j] == target):
# return [i,j]
# j -= 1
</pre>
#### Note:
- 方法2是暴搜
- 方法1是遍历数组建立哈希表，并检查剩余目标分数是否存在哈希表里，在则返回。
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/">167. 两数之和 II - 输入有序数组</a></h3>
<h4>解法</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
# hashmap = {}
# for index,value in enumerate(numbers):
# res = target - value
# if res in hashmap:
# return [hashmap[res]+1,index+1]
# hashmap[value] = index
i = 0
j = len(numbers) - 1
while(j > i):
if numbers[i] + numbers[j] == target:
return [i + 1,j + 1]
# 如果比目标值小，我们将较小元素指针增加一。如果比目标值大，我们将较大指针减小一
elif(numbers[i] + numbers[j] < target):
i += 1
else:
j -= 1
</pre>
#### Note:
- 用前面提到的哈希表做也是可以的 完全相同的解法，时间复杂度O(n)，空间复杂度O(n)
- **双指针解法，充分利用数组已排好序的性质。指针变动条件已在注释中自明，注意这个思想在后面三数之和、四数之和等也会用到**
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/">653. 两数之和 IV - 输入 BST</a></h3>
<h4>解法</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python"># Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def findTarget(self, root: TreeNode, k: int) -> bool:
stack = []
p = root
nums = []
while(stack or p):
if(p):
stack.append(p)
p = p.left
else:
p = stack.pop()
nums.append(p.val)
p = p.right
hashmap = {}
for index,value in enumerate(nums):
res = k - value
if res in hashmap:
return True
hashmap[value] = index
return False
</pre>
#### Note:
- 其实主要是复习了下中序/前序/**后序**（还没整明白） 非递归遍历二叉树。。。
- **我好菜啊 全不会写了。。。唉**
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/3sum/">15. 三数之和</a></h3>
<h4>解法</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution:
def threeSum(self, nums: [int]) -> [[int]]:
nums.sort()
res, k = [],0
for k in range(len(nums)-2):
if nums[k] > 0:
break
if k>0 and nums[k] == nums[k-1]:
continue
i, j = k+1, len(nums) - 1
while(i < j):
s = nums[k] + nums[i] + nums[j]
if(s == 0):
res.append([nums[k], nums[i], nums[j]])
i += 1
j -= 1
while i < j and nums[i] == nums[i-1]:
i += 1
while i < j and nums[j] == nums[j+1]:
j -= 1
elif(s < 0):
i += 1
while i < j and nums[i] == nums[i - 1]:
i += 1
elif(s > 0):
j -= 1
while i < j and nums[j] == nums[j + 1]:
j -= 1
return res
</pre>
#### Note:
- 很多细节 很烦人
- 思想： 遍历数组 记当前下标为i,固定当前下标i，取j = i + 1,k = len(nums) - 1，计算三数之和，再根据实际情况移动j , k。
<h3><a title="题目描述" href="https://leetcode-cn.com/problems/3sum-closest/">16. 最接近的三数之和</a></h3>
<h4>解法</h4>
<pre class="EnlighterJSRAW" data-enlighter-language="python">class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
k = 0
min_flag = float('inf')
res = float('inf')
for k in range(len(nums) - 2):
i, j = k + 1,len(nums) - 1
while(i < j):
s = nums[k] + nums[i] + nums[j]
if(abs(s-target) < min_flag):
min_flag = abs(s-target)
res = s
elif s > target:
j -= 1
else:
i += 1
return res
</pre>
#### Note:
- 比15题简单些，解答案唯一所以不用考虑重复数字的情况。
#### 我太菜了 慢慢来┭┮﹏┭┮
#### 好消息：本站已经开放注册啦。
Leetcode 两数之和&三数之和 5题[双指针]
