算法

滑动窗口

left 是左边界的索引，是在窗口内的最左元素
定长窗口直接算

int left = right - k + 1;//k 是窗口长度

不定长用 while

//这个是典型，left初值是0，给0出边界后left进一
//此时left就指向新窗口的左边界了
//窗口长度就是正常的右减左加一，right-left+1
while (n0 > k) {
    if (nums[left] == 0) n0--;
    left++;
}

二分查找

• 查找 target 第一次出现的索引
• ranges::lower_bound C++20 里引入了这个函数，找下界，下面这就是他的具体实现
• 默认比较器用的 less，就是 mid 值 < target，改用 greater 后就是 mid > target

int n = nums.size();
int left = 0, right = n - 1;//指针初值设为两头
// 循环不变量：整个循环包括结束都会严格满足下面这两个条件
// 循环不变量：看最后左右指针在mid汇合的时候的条件，计算之后左右指针落点
// nums[left-1] < target
// nums[right+1] >= target
// 因为是二分查找，所以最后两指针是相邻的
while ( left <= right ) {//while循环
    int mid = (left + right ) / 2;
    //如果中间值在target左侧，就更新left，缩小左边界
    if (nums[mid] < target) {//这个地方比较的是mid,老错写成left
        //left要设为mid+1，是闭区间最左边界
        left = mid + 1;
    }
    //right要设为mid-1
    else right = mid - 1;
}
return left;//最后返回的是target第一次出现的索引，也等于right+1
//也适用于target不存在的情况，只要记住循环不变量就行
//就比如lower_bound(nums, 0);能返回第一个0的索引
//lower_bound(nums,1);若1不存在能返回第一个大于0的索引

• lower_bound(nums.begin(),nums.(end),target)，升序，找到第一个>=target 的值的元素，并返回该元素的迭代器
• lower_bound( begin , end , val , less<type>() )升序，找到第一个>=target 的元素，与上面不写的升序功能相同,官方的自定义比较函数
• lower_bound( begin , end , val , greater<type>() )降序，找到第一个<=target 的元素
• 返回的值是迭代器，若要获取索引，需要用- begin
• ranges::lower_bound(nums2.begin(),nums2.end(), nums1[i], ranges::greater{}) - nums2.begin();//减去开始获取索引
• upper_bound()也是升序，但是是找到第一个>target 的元素

前缀和

s[i]就是前 i 个元素的和
适合求区间和，无论是否有序

// 建立前缀和数组
vector<int> s;
s.resize(nums.size() + 1);// 常用resize(n + 1)
for (int i = 0; i < nums.size(); i++) {
    // 第一位就是0，计算[left, right]区间的和就是s[right + 1] - s[left]
    s[i + 1] = s[i] + nums[i];
}

找所有和为 k 的子串

for (int i = 0 ; i < pre.size(); i++) {// i是正在遍历的数组，j是要查的
    // 等式变换pre[i] - pre[j] = k; pre[j] = pre[i] - k;
    auto it = map.find(pre[i] - k);// find返回迭代器
    if (it != nullptr) ans += it -> second;
    // 用元素当key，频率当value
    map[pre[i]]++;
}

链表 List

翻转链表

ListNode* reverseList(ListNode* node) {
        ListNode* pre = nullptr, *cur = node;
        while (cur != nullptr) {
            ListNode* nxt = cur -> next;// nxt每次重新赋值
            cur -> next = pre;// 一次只改一个next指向
            pre = cur;// 注意顺序，先把cur赋出去，再覆盖cur
            cur = nxt;
        }
        return pre;// 最后返回新链表的头结点
    }

快慢指针法，查看是否存在环型链表

bool hasCycle(ListNode *head) {
    // 定义快慢指针
    ListNode* fast = head, *slow = head;
    // 省略 != nullptr
    while (fast && fast -> next) {
        // 快指针每次走两步，慢指针每次走一步
        slow = slow -> next;
        fast = fast -> next -> next;
        if (fast == slow) return true;// 有环的会一直打转直到相遇
    }
    return false;
}

快慢指针法，找中间节点

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast != nullptr && fast -> next != nullptr) {
        slow = slow -> next;
        fast = fast -> next -> next;
    }
    return slow;// 奇数返回中间，偶数返回中间右侧第一个
}

虚拟头结点，头插法，合并两个有序链表

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0); // 虚拟头节点
    ListNode* tail = &dummy;
    // 直到走空一个链表为止
    while (list1 != nullptr && list2 != nullptr) {
        if (list1 -> val <= list2 -> val) {
            // 比较此时两个链表谁的val大
            tail -> next = list1;
            // 然后链表走一步继续比较
            list1 = list1 -> next;
        }
        else {
            tail -> next = list2;
            list2 = list2 -> next;
        }
        // 上面确定了tail的next，这里走一步到最新节点
        tail = tail -> next;
    }
    // 因为是有序的，所以后面的直连接第一个节点就行，谁存在就连接谁
    tail -> next = list1 ? list1 : list2;
    return dummy.next;
}

二叉树

深度优先搜索(DFS)，用递归或者栈实现

// 递归中序遍历
void Recursion(TreeNode* root, vector<int> &ans) {
    if (root == nullptr) return;// 终止条件
    Recursion(root->left, ans);// 记得把数组地址传进去
    ans.push_back(root->val);
    Recursion(root->right, ans);
}
// 栈中序遍历，一句话的核心思想：一路向左，走到头；弹出处理，转右再走左。
stack<TreeNode*> stk;
// 只要存在结点或者栈不空就进行，直到结点和栈都空
while (root != nullptr || !stk.empty()) {
    // 先把结点左子树全压进去
    while (root != nullptr) {
        stk.push(root);
        root = root->left;
    }
    // 出来之后的root是空，先把栈里最先结点赋回去
    // 每次while循环都会取出最新的结点
    root = stk.top();
    // 当前结点不存在左子树，把值放进数组，进行中序遍历
    ans.push_back(stk.top()->val);
    stk.pop();
    // 最后root再更新成右子树
    root = root->right;
}

广度优先搜索(BFS)，用队列实现

// BFS广度优先遍历，用队列来打成，先进后出
// 用队列存储指针
queue<TreeNode*> queue;
// 二维向量存储结果
vector<vector<int>> res;
queue.push(root);
while (!queue.empty()) {
    // 构建一行
    vector<int> vals;
    // 每次把上一轮存进来的子节点都遍历完
    for(int n = queue.size(); n > 0; n--) {
        // 获取当前结点
        TreeNode* node = queue.front();
        // 把当前结点的左右子树推进队列
        if (node->left) queue.push(node->left);
        if (node->right) queue.push(node->right);
        // 把结点的值放入向量
        vals.push_back(node->val);
        // 弹出尾结点
        queue.pop();
    }
    // 把构建的一行放入答案
    res.emplace_back(vals);
}
return res;

递归

把原问题化解成一个个和相似的子问题，然后确定好递归的终止条件

数组转换为平衡二叉树

// 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
TreeNode* dfs(vector<int>& nums, int left, int right) {
    if (left == right) return nullptr;
    int m = (left + right) / 2;
    TreeNode* node = new TreeNode(nums[m]);
    node->left = dfs(nums, left, m);
    node->right = dfs(nums, m+1 , right);
    return node;
    // 也可以直接用构造函数写返回值，第一个参数是val，第二个是左子树，第二个是右子树
    // return new TreeNode(m, dfs(nums, left, m), dfs(nums, m+1, right))
}

二叉搜索树，左子树严格小于根节点，右子树严格大于根节点
中序遍历就是升序