基础算法模板

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] >= target
            int 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;
    }
}