1. 相向双指针

class Solution {  // 两数之和public int[] twoSum(int[] numbers, int target) {int left = 0; // 第一步初始化开头和结尾两个指针int right = numbers.length - 1;while (true) { // 之后一直while循环  int s = numbers[left] + numbers[right]; //计算左右两个指针对应的和 比较当前值和目标值的范围if (s == target) {return new int[]{left + 1, right + 1}; // 题目要求下标从 1 开始}if (s > target) { right--;} else {left++;}}}
}

前提：需要数组是有序的

步骤：

1. 第一步初始化左右两个节点
2. 第二步while一直循环 while（true）
3. while内计算左右两个值的和
4. 三种情况 比较当前值 和 目标值的关系

// 三数之和
1、取出其中一个数值，然后取反，让另外两个数的和 和 这个数相加等于0 然后使用两数只和
2、题目的顺序没有关系 所以对于要确定一个顺序

盛水最多的容器：
同样是左边一个指针，右边一个指针，之后依次移动当前左右两边的最小值
结束条件： while（left > right）

接雨水
当前这个位置能接多少水，取决于当前这个位置左边的最大高度和右边的最大高度
所以从左往右计算当前这个位置的最大值，计算一个数组从右往左计算当前这个位置的最大值，计算一个数组依次计算当前这个位置能有多少水，分别是当前这个位置左边的最大值 - 右边的最大值 然后取绝对值

滑动窗口

class Solution {public int minSubArrayLen(int target, int[] nums) {int n = nums.length;int ans = n + 1;int sum = 0; // 子数组元素和int left = 0; // 子数组左端点for (int right = 0; right < n; right++) { // 枚举子数组右端点sum += nums[right];while (sum >= target) { // 满足要求ans = Math.min(ans, right - left + 1);sum -= nums[left++]; // 左端点右移}}return ans <= n ? ans : 0;}
}

步骤：

1. 初始化一个左端点（从左边开始）
2. 初始化当前所有结果的值
3. 一个for循环 用户遍历右端点
4. for循环内，首先将当前的值加上，判断现在是否符合条件，依次将左端点向右边延伸

总结：
右端点增加资源 左端点减少资源 左减右增
判断当前是否符合情况（都是用while 如果是大小关系，使用while进行判断是否大于小于
也可以用while判断是否存在）

##二分查找

    // 闭区间写法private int lowerBound(int[] nums, int target) {int left = 0, right = nums.length - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量：// nums[left-1] < target// nums[right+1] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right]} else {right = mid - 1; // 范围缩小到 [left, mid-1]}}return left;}

步骤：

1. 初始化左右两个端点，其中左端点指向0，右端点指向最后一个值
2. 使用while（left <= right）判断是否循环结束
3. 计算mid的位置，计算的时候使用left + （right - left）/ 2进行计算
4. 判断nums[mid] 和 target的大小关系 （这里只需要两个判断就可以）
5. 当while结束的时候返回left的位置 就是目标的位置

其他：
如果当前值有多个，可以首先计算比当前值小于1的位置，比如target是7，那么就计算目标值是6的位置，得出的位置 + 1就是目标位置

如果所有的值都 < target,那么left会一直向后面进行移动
同样，如果所有的值都 > target,right会一直向前面进行移动，最终left会等于right

反转链表

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null, cur = head;while (cur != null) {ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}return pre;}
}

步骤：

1. pre = null cur = head
2. 使用while（cur != null）
3. 依次变换nxt cur.next pre cur
4. return pre

内容：最后 pre当前的值，也可以说是最后的一个值 cur指向的是最后一个值的下一个值

快慢指针

class Solution {public ListNode middleNode(ListNode head) {ListNode slow = head, fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}

步骤：

1. 初始化slow和fast指针
2. 使用while判断fast指针是否到达了null 具体是 fast != null && fast.next != null

计算二叉树的深度 最大深度或者最小深度

方法1：自顶向下
依次递归遍历当前是否到达叶子节点，如果没有的话，就 + 1，如果有的话 就更新答案
优化：如果查找到当前节点的深度已经是大于或者小于一个节点的值，那么就可以跳过之后的步骤了

方法2：自底向上
如果当前没有左子树，那么当前的深度为右子树 + 1
如果当前没有右子树，那么当前的深度为左子树 + 1
如果当前有左子树和右子树，那么当前的深度是 min（左子树，右子树）+ 1

判断是叶子节点使用： node.left == node.right

二叉树的前序遍历 中序遍历 后序遍历

前序遍历

class Solution {public boolean isValidBST(TreeNode root) {return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean isValidBST(TreeNode node, long left, long right) {if (node == null) {return true;}long x = node.val;return left < x && x < right &&isValidBST(node.left, left, x) &&isValidBST(node.right, x, right);}
}

思路：如果当前节点是空节点，就返回true，说明是二叉搜索胡
接着就以根 左 右进行遍历
return的时候直接判断 当前节点 和 左节点 右节点之间的关系

中序遍历

class Solution {private long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) {return true;}if (!isValidBST(root.left) || root.val <= pre) {return false;}pre = root.val;return isValidBST(root.right);}
}

中序遍历需要知道的就是得到的是一个 递增序列
步骤：

1. 初始化 pre节点，并且设置成为最大值
2. 判断当前node是否是null，如果是的话 返回 true
3. 判断左节点是否是二叉搜索树 并且判断当前节点的值是否发是 node.val <= pre (正常来说当前节点是需要大于pre节点的，这是因为得到的是一个递增的序列，如果当前的值暂时还没有原来的值大，说明现在并不是一个二叉搜索树)
4. 更新pre的值为当前这个node的值
5. 最后判断右子树是否是一个二叉搜索树

后序遍历

class Solution {public boolean isValidBST(TreeNode root) {return dfs(root)[1] != Long.MAX_VALUE;}private long[] dfs(TreeNode node) {if (node == null) {return new long[]{Long.MAX_VALUE, Long.MIN_VALUE};}long[] left = dfs(node.left);long[] right = dfs(node.right);long x = node.val;// 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了if (x <= left[1] || x >= right[0]) {return new long[]{Long.MIN_VALUE, Long.MAX_VALUE};}return new long[]{Math.min(left[0], x), Math.max(right[1], x)};}
}

思路：使用一个返回的数组进行判断，正常的形式是 {min,max}
步骤：

1. 首先如果当前节点是null，返回 （max，min）
2. 计算左右子树的数组，得到当前的值x
3. 判断如果x <= left[1] (也就是左子树的最大值) 或者 x >= right[0] （也就是右子树的最小值），直接返回 一个类似于 false的结果
4. 返回 当前值和 左子树最小值的最小值 右子树最大值和当前值的最大值

层序遍历

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {if (root == null) return List.of();List<List<Integer>> ans = new ArrayList<>();Queue<TreeNode> q = new ArrayDeque<>();q.add(root);while (!q.isEmpty()) {int n = q.size();List<Integer> vals = new ArrayList<>(n); // 预分配空间while (n-- > 0) {TreeNode node = q.poll();vals.add(node.val);if (node.left != null)  q.add(node.left);if (node.right != null) q.add(node.right);}ans.add(vals);}return ans;}
}