两数之和-双指针

1.1、1. 两数之和

1.2、167. 两数之和 II - 输入有序数组

class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: i = 0 j = len(numbers)-1 while i < j: s = numbers[i] + numbers[j] if s == target: return [i+1, j+1] elif s < target: i += 1 else: j -= 1 return []

1.3、653. 两数之和 IV - 输入 BST

中序遍历+双指针

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def __init__(self) -> None: self.res = [] def findTarget(self, root: TreeNode, k: int) -> bool: if not root: return False self.preOrder(root) i = 0 j = len(self.res)-1 while i < j: s = self.res[i] + self.res[j] if s == k: return True elif s < k: i += 1 else: j -= 1 return False # 二叉搜索树， 中序遍历，是一个升序序列 def preOrder(self, root: TreeNode) -> None: if root.left: self.preOrder(root.left) self.res.append(root.val) if root.right: self.preOrder(root.right)