目录
一、排序算法
1、冒泡排序
2、快速排序
3、归并排序
4、堆排序
5、插入排序
6、topK
二、二分查找
1.一维数组二分查找
2.二维数组二分查找
3.寻找旋转排序数组中的最小值
三、有序数组的平方（双指针法）
四、LRU算法
五、二叉树
1.前、中、后序遍历（递归法和迭代法）
2.层序遍历
3.对称二叉树
4.二叉树翻转
5.二叉树的深度
6.平衡二叉树
7.树的子结构
8. 重建二叉树
9.从上到下打印二叉树 III
10.二叉搜索树的后序遍历序列
11.二叉树中和为某一值的路径
12.二叉搜索树与双向链表
13.序列化二叉树
14.二叉搜索树的最近公共祖先
15.二叉树的最近公共祖先
16.把二叉搜索树转换为累加树
六、链表
1.构建链表
2.链表反转
3.两两交换链表中的节点
4.删除倒数第n个节点
5.链表排序
6.中间部分链表反转
7.合并两个链表
8.合并K个链表
9.删除链表的节点
10.链表中倒数第k个节点
11.环形链表
12.环形链表 II
七、栈
1.用两个栈实现队列
2.包含min函数的栈
八、动态规划
1.斐波那契函数
2.青蛙跳台阶问题
3.连续子数组的最大和
4.剪绳子
5.礼物的最大价值或者最短路径
6.丑数
7.n个骰子的点数
8.股票的最大利润
9.最佳买卖股票时机含冷冻期
九、数组
1.调整数组顺序使奇数位于偶数前面
2.最短无序连续子数组
十、其他
1.二进制数中1的个数（汉明距离）
十一、哈希表
1.两数之和
2.有效的括号
3.和为 K 的子数组
// 冒泡排序.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
int main()
{
int n = 6;
int a[] = {8,2,6,5,1,7};
//从第0位到倒数第一位开始判断
for (int i = 0; i < n-1; i++)
{
//开始判断的轮数
for (int j = 0; j < n- 1 - i; j++)
{
//如果前一个数大于后一个数，则交换
if (a[j] > a[j+1])
{
int temp;
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (int k = 0; k < n; k++)
{
std::cout << a[k] << std::endl;
}
//system("pause");
return 0;
}
思路：先设置数组最左端为基准参考值，然后小于基准值的都移到左边，大于基准值的都移到右边，然后对左右分别再进行快排，时间复杂度O(nlogn)。
#include<iostream>
using namespace std;
void quickSort(int a[],int low,int height)
{
if (low < height)
{
int i = low, j = height;
int base = a[low];
//如果i<j则一直循环
while (i < j)
{
//首先从右往左找，如果右边值大于base，则j--
while (i < j&&a[j] >= base)
{
j--;
}
//上一句while结束，代表在右边找到小于base的值，此时把右边的值放在i所在的位置
if (i < j)
{
a[i] = a[j];
//放完后i向右移动一位
i++;
//上面两句其实可以合为一句
//a[i++] = a[j];
}
//开始准备从左往右找大于base的值，如果大于base，则放在右边j的位置上
while (i < j&&a[i] <= base)
{
i++;
}
//上面一句while执行完，代表左边找到大于base的值，准备将其移到右边
if (i < j)
{
a[j] = a[i];
j--;
//同样，以上两句可以合并为一句
//a[j--] = a[i];
}
}
//以上大while执行完，代表i和j移动到同一个位置，此时把base设置到中间i和j的位置上
a[i] = base;
//其实也可以写为
//a[j] = base;
//接着对base两边的两个数组再进行快速排序，也就是递归
quickSort(a, low, i - 1);
quickSort(a, i + 1, height);
}
}
int main()
{
int a[6] = {5,3,1,2,4,6};
quickSort(a,0,5);
for (int i = 0; i < 6; i++)
{
cout << a[i] << " ";
}
return 0;
}处理思路：把一个无序数组，从中间分开，分为左右两部分，然后对左右两部分再进行二分，最后分为各1个元素，此时对单独的一个元素排序，排好再合并。
#include <iostream>
//子块排序合并函数
void merge(int a[], int l, int m, int r, int t[])
{
int i = l;
int j = m + 1;
int k = l;
//如果循环都在
while (i <= m && j <= r)
{
//如果a[i]<=a[j]
if (a[i] <= a[j])
{
t[k++] = a[i++];
}
else
{
t[k++] = a[j++];
}
}
while (i <= m)
{
t[k++] = a[i++];
}
while (j<=r)
{
t[k++] = a[j++];
}
//把排序后的数组放进原数组
for (int p =l;p <= r; p++)
{
a[p] = t[p];
}
}
//分开函数
void mergeSort(int a[],int low,int height, int temp[])
{
//left和right的中间元素
int mid = (low + height) / 2;
//递归结束条件,如果分组后，只剩一个元素，就结束
if (low == height)
return;
//对左边数组分组
mergeSort(a,low,mid,temp);
//对右边数组分组
mergeSort(a,mid+1,height,temp);
//对两数组排序并合并
merge(a,low,mid,height,temp);
}
int main()
{
int a[] = { 2,1,5,4,1,9,8,3,7 ,6};
int temp[10];
mergeSort(a, 0, 9, temp);
for (int i = 0; i < 10; i++)
{
std::cout << a[i] << " ";
}
}
引入大顶堆概念，首先把数组构建成大顶堆结构，堆顶为最大值，然后把堆顶和数组末尾的值交换，接着重新维护大顶堆，直到找到第二个最大值，再将其交换到倒数第二位，后面重复，直到排序出升序数组。
#include <iostream>
using namespace std;
//维护大顶堆结构的函数
void adjust(int a[],int n,int index)//维护index处二叉树的堆结构
{
//根据堆结构确定index的左右子节点序号
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
//设置当前堆最大序号
int maxIndex = index;
//如果左子节点大于最大值，把最大序号设为左子节点序号
if (leftChild < n&&a[maxIndex] < a[leftChild])
maxIndex = leftChild;
//如果右子节点大于最大值，更新最大值序号为右子节点
if (rightChild < n&&a[maxIndex] < a[rightChild])
maxIndex = rightChild;
//如果最大序号不是初始默认的根节点index，则说明左右子节点中有大于index的节点，需要将最大值放到index位置，然后维护堆
if (maxIndex != index)
{
//把最大值移到index处
swap(a[maxIndex], a[index]);
adjust(a, n, maxIndex);//经过上一步交换，较小值被放在a[maxIndex]中，对其及子节点再进行堆结构维护
}
}
//堆排序
void heapSort(int a[],int n)
{
//首先构建基础堆结构,根据根节点生成堆结构
//从后往前，完全二叉树最后一个值为n-1,其父节点为((n-1)-1)/2,此时其左边往前全为根节点
for (int i = (n - 2) / 2; i >= 0; i--)
{
//根据数组建大顶堆堆
adjust(a,n,i);
}
//然后排序，每次建堆，把堆顶元素插入数组末尾
for (int i = n - 1; i > 0; i--)
{
//把末尾的一个数与堆顶交换
swap(a[0],a[i]);//此时已经把大顶堆的堆顶放在数组最后面了, n-3 n-2 n-1
//然后维护堆结构，重新找到新的堆顶
adjust(a,i,0);//把末尾最后一个较小的数，放在堆顶重新维护
}
}
int main()
{
int a[] = {2,5,6,3,1,4,8,9,7,2};
heapSort(a,10);
for (int i : a)
cout << i << " ";
}从i=1循环数组，然后记录当前值，当前值以前为排序好的，然后依次判断当前值和前面已排好序列的大小，最后把当前值插在合适的地方。
#include <iostream>
using namespace std;
void insertSort(int a[],int n)
{
//从第一个元素开始往后遍历
for (int i = 1; i < n; i++)
{
//每次判断当前元素和之前已排好序元素的最后一位的大小
int j = i - 1;
//记录当前值
int key = a[i];
while ((j >= 0) && key < a[j])
{
//当前元素小于已排好序的最后一个元素，则将其后移，方便把key插入其原位置
a[j + 1] = a[j];
j--;
//以上两句也可以简写为
//a[j + 1] = a[j--];
}
//把i位置的值插到前边顺序数组的对应位置
a[j + 1] = key;
}
}
int main()
{
int a[6] = { 5,3,1,2,4,6 };
insertSort(a,6);
for (int i = 0; i < 6; i++)
{
cout << a[i] << " ";
}
return 0;
}
//使用sort
class Solution1 {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
//首先通过map存储数字对应出现的频率
unordered_map<int,int> mp;
for(int i=0;i<nums.size();i++)
{
mp[nums[i]]++;
}
vector<int> res;
for(auto [key,val]:mp)
{
res.emplace_back(key);
}
//然后对map进行排序
sort(res.begin(),res.end(),[&](int &a,int &b)->bool{
return mp[a]==mp[b]?a<b:mp[a]>mp[b];
});
//最后将k后面的移除掉
res.erase(res.begin()+k,res.end());
return res;
}
};
//使用归并排序
class Solution {
public:
struct cmp{
bool operator()(pair<int,int>a,pair<int,int>b){
return a.second>b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
//首先通过map存储数字对应出现的频率
unordered_map<int,int> mp;
for(int i=0;i<nums.size();i++)
{
mp[nums[i]]++;
}
//用小顶堆
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
for(auto x:mp){
q.push(x);
if(q.size()>k){
q.pop();
}
}
vector<int>res;
while(!q.empty()){
res.push_back(q.top().first);
q.pop();
}
return res;
}
};问题描述：给定一个升序的数组nums，再给定一个target值，如果nums里存在target，则返回其下标，如果不存在，则返回-1。
解题思路：设置一个左下标left，一个右下标right，一个中间下标middle，由于列表升序，所以通过判断middle与target的大小，就能判断target在左边还是右边，从而降低比对次数，时间复杂度O(logn)。
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;
while(left<=right)
{
int middle=(left+right)/2;
if(nums[middle]>target)
{
right=middle-1;
}
else if(nums[middle]<target)
{
left=middle+1;
}
else
{
return middle;
}
}
return -1;
}
};class Solution1 { //暴力搜索
public:
bool Find(int target, vector<vector<int> > array) {
for(auto i:array){
for(auto j:i){
if(j==target) return true;
}
}
return false;
}
};
class Solution { //二分查找
public:
bool binarySearch(vector<int> nums,int target){
int i=0;
int j=nums.size()-1;
while(i<=j){
int m=(i+j)/2;
if(nums[m]>target) j=m-1;
else if(nums[m]<target) i=m+1;
else return true;
}
return false;
}
bool Find(int target, vector<vector<int> > array) {
for(auto i:array){
if(binarySearch(i,target)) return true;
}
return false;
}
};class Solution {
public:
int findMin(vector<int>& nums) {
int i=0;
int j=nums.size()-1;
while(i<j){
int m=(i+j)/2;
if(nums[m]<nums[j]) j=m;
else i=m+1;
}
return nums[i];//i和j相同
}
};问题描述：给定一个非递减排序的数组，将该数组每个元素平方后，也按非递减排序输出
示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]
解题思路：
1.先对每个元素平方，然后排序，时间复杂度为O(n+nlogn)
2.由于输入数组升序，平方后数组两边最大，中间最小，此时可以使用双指针法，从两边开始比较，把最大值插入新数组最后方。
class Solution {
public:
vector<int> sortedSquares(vector<int>& A)
{
int k=A.size()-1; //新数组下标
vector<int>res(A.size(),0);
for(int i=0,int j=A.size()-1;i<=j;)
{
if(A[i]*A[i]<A[j]*A[j])
{
res[k--]=A[j]*A[j];
j--;
}
else if(A[i]*A[i]>A[j]*A[j])
{
res[k--]=A[i]*A[i];
i++;
}
}
return res;
}最近最常用算法，相当于最近搜索，需要用到链表，哈希表，链表容量。放入数据时，先判断哈希表里有没有，没有往链表头部插入，如果链表大小超过链表容量，删除链表最后一个。如果哈希表内有，则移到链表头部。取出数据时，如果哈希表内有，则将该节点的值返回，并将其移到链表首部，如果没有，则返回-1。
class LRUCache {
list<pair<int, int>> cache;//创建双向链表
unordered_map<int, list<pair<int, int>>::iterator> map;//创建哈希表
int cap;
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
if (map.count(key) > 0){
auto temp = *map[key];
cache.erase(map[key]);
map.erase(key);
cache.push_front(temp);
map[key] = cache.begin();//映射头部
return temp.second;
}
return -1;
}
void put(int key, int value) {
if (map.count(key) > 0){
cache.erase(map[key]);
map.erase(key);
}
else if (cap == cache.size()){
auto temp = cache.back();
map.erase(temp.first);
cache.pop_back();
}
cache.push_front(pair<int, int>(key, value));
map[key] = cache.begin();//映射头部
}
};前序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//递归法
class Solution2 {
public:
void traversal(TreeNode*cur,vector<int>&vec){
//终止条件
if(cur==nullptr)return;
//根左右
vec.push_back(cur->val);
traversal(cur->left,vec);
traversal(cur->right,vec);
}
vector<int> preorderTraversal(TreeNode* root) {
//创建结果集合
vector<int>ans;
traversal(root,ans);
return ans;
}
};
//迭代法
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
st.push(root);
//创建结果集合
vector<int>ans;
if(root==nullptr) return ans;
//循环迭代
while(!st.empty()){//如果栈不为空
TreeNode*temp=st.top();
//先把根节点出栈
st.pop();
ans.push_back(temp->val);
if(temp->right) st.push(temp->right);
if(temp->left) st.push(temp->left);
}
return ans;
}
};中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//递归法
class Solution1 {
public:
void traversal(TreeNode*cur,vector<int>&vec){
if(cur==nullptr)return;
//左根右
traversal(cur->left,vec);
vec.push_back(cur->val);
traversal(cur->right,vec);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>ans;
traversal(root,ans);
return ans;
}
};
//迭代法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
vector<int>ans;
TreeNode*cur=root;
while(!st.empty()||cur!=nullptr){
if(cur!=nullptr){
st.push(cur);
cur=cur->left;
}else{
cur=st.top();
st.pop();
ans.push_back(cur->val);
cur=cur->right;
}
}
return ans;
}
};后序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//递归法
class Solution1 {
public:
void traversal(TreeNode*cur,vector<int>&vec){
if(cur==nullptr)return;
//左右根
traversal(cur->left,vec);
traversal(cur->right,vec);
vec.push_back(cur->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int>ans;
traversal(root,ans);
return ans;
}
};
//迭代法
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*>st;
st.push(root);
vector<int>ans;
if(root==nullptr)return ans;
while(!st.empty()){
TreeNode*temp=st.top();
st.pop();
ans.push_back(temp->val);
if(temp->left) st.push(temp->left);
if(temp->right) st.push(temp->right);
}
reverse(ans.begin(),ans.end());
return ans;
}
};/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//递归法
class Solution {
public:
void traversal(TreeNode*cur,vector<vector<int>>&res,int depth){
//递归终止条件
if(cur==nullptr) return;
if(res.size()==depth) res.push_back(vector<int>());
res[depth].push_back(cur->val);
if(cur->left) traversal(cur->left,res,depth+1);
if(cur->right) traversal(cur->right,res,depth+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>ans;
traversal(root,ans,0);
return ans;
}
};
//迭代法
class Solution2 {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>ans;
if(root==nullptr)return ans;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int num=q.size();
vector<int>vec;
for(int i=0;i<num;i++){
TreeNode*temp=q.front();
q.pop();
vec.push_back(temp->val);
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
ans.push_back(vec);
}
return ans;
}
};class Solution {
public:
bool isSymmetric(TreeNode* root) {
return check(root,root);
}
bool check(TreeNode*l,TreeNode*r){
if(!l&&!r) return true; //如果都为空
if(!l||!r) return false;
return l->val==r->val&&check(l->left,r->right)&&check(l->right,r->left);
}
};/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
//递归法
class Solution1 {
public:
TreeNode* invertTree(TreeNode* root) {
//递归终止条件
if(root==nullptr) return root;
swap(root->left,root->right);
if(root->left) invertTree(root->left);
if(root->right) invertTree(root->right);
return root;
}
};
//迭代法
//1.深度优先遍历 前序 根左右
class Solution2 {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr) return root;
stack<TreeNode*>st;
st.push(root);
while(!st.empty()){
TreeNode*temp=st.top();
st.pop();
swap(temp->left,temp->right);
if(temp->left) st.push(temp->left);
if(temp->right) st.push(temp->right);
}
return root;
}
};
//2.广度优先遍历 层序
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==nullptr) return root;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int num=q.size();
for(int i=0;i<num;i++){
TreeNode*cur=q.front();
q.pop();
if(cur->left) q.push(cur->left);
if(cur->right) q.push(cur->right);
swap(cur->left,cur->right);
}
}
return root;
}
};class Solution1 {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr) return 0;
vector<vector<int>>res;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
vector<int>k;
int num=q.size();
for(int i=0;i<num;i++){
TreeNode*t=q.front();
q.pop();
k.push_back(t->val);
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
res.push_back(k);
}
return res.size();
}
};
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root==nullptr) return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};class Solution { //由二叉树最大深度引申而来
public:
bool isBalanced(TreeNode* root) {
if(!root) return true;
int left=getMaxDepth(root->left);
int right=getMaxDepth(root->right);
return abs(left-right)<=1&&isBalanced(root->left)&&isBalanced(root->right);
return true;
}
int getMaxDepth(TreeNode*root){
if(!root) return 0;
int left=getMaxDepth(root->left);
int right=getMaxDepth(root->right);
return max(left,right)+1;
}
};class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(A==nullptr||B==nullptr) return false;
return isSub(A,B)||isSubStructure(A->left,B)||isSubStructure(A->right,B);
}
bool isSub(TreeNode*A,TreeNode*B){
if(B==nullptr) return true; //如果子树遍历完，则说明匹配
if(A==nullptr) return false; //如果待匹配二叉树遍历完，则说明没匹配上
if(A->val!=B->val) return false; //如果值不等，则不匹配
return isSub(A->left,B->left)&&isSub(A->right,B->right);
}
};
class Solution {
public:
unordered_map<int,int>mp;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n=preorder.size();
//构建map
for(int i=0;i<inorder.size();i++){
mp[inorder[i]]=i;
}
return traverse(preorder,0,n-1,inorder,0,n-1);
}
TreeNode* traverse(vector<int>& pre,int l1,int r1,vector<int>&ino,int l2,int r2){
//递归终止条件
if(l1>r1) return nullptr;
//创建根节点
TreeNode*root=new TreeNode(pre[l1]);//前序遍历的第一个数就是根节点
//寻找根节点在中序遍历中的序号i
int i=mp[pre[l1]];
root->left=traverse(pre,l1+1,l1+(i-l2),ino,l2,i-1);
root->right=traverse(pre,l1+i-l2+1,r1,ino,i+1,r2);
return root;
}
};class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>>res;
bool fromLeft=true;
if(root==nullptr) return res;
queue<TreeNode*>q;
q.push(root);
while(!q.empty()){
int num=q.size();
deque<int>temp;
for(int i=0;i<num;i++){
TreeNode*t=q.front();
q.pop();
if(fromLeft){
temp.push_front(t->val); //从队头插入，顺序
}else{
temp.push_back(t->val); //从队尾插入，逆序
}
if(t->right) q.push(t->right);
if(t->left) q.push(t->left);
}
fromLeft=!fromLeft;
res.push_back(vector<int>{temp.begin(),temp.end()});
}
return res;
}
};剑指offer|题目33二叉搜索树的后序遍历序列_哔哩哔哩_bilibili
class Solution {
public:
vector<int>res;
bool dfs(int l,int r){
if(l>=r) return true; //递归结束条件
int root=res[r]; //根节点
int k=l;
while(k<r&&res[k]<root) k++;
for(int i=k;i<r;i++){
if(res[i]<root) return false; //如果右子树小于根节点，则不是二叉搜索树
}
return dfs(l,k-1)&&dfs(k,r-1);
}
bool verifyPostorder(vector<int>& postorder) {
res=postorder;
if(res.empty()) return true;
return dfs(0,res.size()-1);
}
};【剑指Offer最优解】 34. 二叉树中和为某一值的路径 ｜ 暑假拿捏leetcode_哔哩哔哩_bilibili
class Solution {
public:
//先创建结果集和临时路径
vector<vector<int>>res;
vector<int>temp;
vector<vector<int>> pathSum(TreeNode* root, int target) {
if(root==nullptr) return res;
dfs(root,target);
return res;
}
//深度优先+回溯
void dfs(TreeNode*root,int target){
//递归结束条件
if(root==nullptr) return;
//从根节点开始压入数据
temp.push_back(root->val);
target-=root->val;
//如果遍历到叶子节点，并且此时target==0,则将路径压入结果集
if(root->left==nullptr&&root->right==nullptr&&target==0) res.push_back(temp);
//如果没结束则继续遍历左右子树
dfs(root->left,target);
dfs(root->right,target);
//回溯 删除临时路径最后一个元素
temp.erase(temp.end()-1,temp.end());
}
};【剑指Offer最优解】 36. 二叉搜索树与双向链表 ｜ 基础功_哔哩哔哩_bilibili
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
//保存中序遍历的结果集
vector<Node*>res;
void tranverse(Node*root){
if(root==nullptr) return;
tranverse(root->left);
res.push_back(root);
tranverse(root->right);
}
Node* treeToDoublyList(Node* root) {
if(root==nullptr) return nullptr;
//采用中序遍历，结果依次由小到大排序
tranverse(root);
Node*head=res[0];
Node*pre=head;
for(auto x:res){
pre->right=x;
x->left=pre;
pre=x;
}
pre->right=head;
head->left=pre;
return head;
}
};class Codec { //递归法
public:
void rserialize(TreeNode*root,string &str){
if(root==nullptr){
str+="null,"; //当前节点为null时，往str后面加入null,
}else{
str+=to_string(root->val)+","; //如果有内容则插入该数据
//遍历左右子树
rserialize(root->left,str);
rserialize(root->right,str);
}
}
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
rserialize(root,res);
return res;
}
TreeNode* rdeserialize(list<string>&lst){
if(lst.front()=="null"){
lst.erase(lst.begin());
return nullptr;
}
int val=stoi(lst.front());
TreeNode*root=new TreeNode(val);
lst.erase(lst.begin());
//重建左右子树
root->left=rdeserialize(lst);
root->right=rdeserialize(lst);
return root;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
//首先把string里每个节点取出来，放进list里面，然后再重建
list<string>lst;
string str;
for(auto&x:data){
if(x==','){
lst.push_back(str);
str.clear();
}else{
str.push_back(x);
}
}
if(!str.empty()){
lst.push_back(str);
str.clear();
}
return rdeserialize(lst);
}
};
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先_哔哩哔哩_bilibili
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr) return nullptr;
//如果在左子树，则递归
if(p->val<root->val&&q->val<root->val) return lowestCommonAncestor(root->left,p,q);
//如果在右子树，则递归
if(p->val>root->val&&q->val>root->val) return lowestCommonAncestor(root->right,p,q);
//否则直接返回根节点（代表pq分布在左右两边）
return root;
}
};剑指68 II 二叉树的最近公共祖先_哔哩哔哩_bilibili
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==nullptr) return root;
//如果root等于左子树或者等于右子树，则直接返回root
if(root->val==p->val||root->val==q->val) return root;
//向左或者向右寻找pq的最近祖先
TreeNode*leftPatrnt=lowestCommonAncestor(root->left,p,q);
TreeNode*rightParent=lowestCommonAncestor(root->right,p,q);
//如果左边为空，则pq都在右边
if(leftPatrnt==nullptr) return rightParent;
else if(rightParent==nullptr) return leftPatrnt;
else return root; //若pq分别在两边，则返回根节点
}
};Leetcode 538. 把二叉搜索树转换为累加树_哔哩哔哩_bilibili
class Solution {
public:
int sum=0;
TreeNode* convertBST(TreeNode* root) {
if(root!=nullptr){
//右 根 左
convertBST(root->right);
sum+=root->val;
root->val=sum;
convertBST(root->left);
}
return root;
}
};#include <iostream>
class MyLinkedList {
public:
struct LinkList {
int val;
LinkList*next;
LinkList(int val) :val(val), next(nullptr) {}
};
LinkList*dum;
int size;
MyLinkedList() {
dum = new LinkList(0);
size = 0;
}
int get(int index) {
if (index > (size - 1) || index < 0) {
return -1;
}
else {
LinkList*t = dum->next;
while (index--) {
t = t->next;
}
return t->val;
}
}
void addAtHead(int val) {
LinkList*t = new LinkList(val);
t->next = dum->next;
dum->next = t;
size++;
}
void addAtTail(int val) {
LinkList*t = dum;
while (t->next) {
t = t->next;
}
LinkList*newt = new LinkList(val);
t->next = newt;
size++;
}
void addAtIndex(int index, int val) {
if (index > size) {
return;
}
else {
LinkList*t = dum;
while (index--) {
t = t->next;
}
LinkList*newt = new LinkList(val);
newt->next = t->next;
t->next = newt;
}
size++;
}
void deleteAtIndex(int index) {
if (index >= size || index < 0) {
return;
}
else {
LinkList*t = dum;
while (index--) {
t = t->next;
}
t->next = t->next->next;
size--;
}
}
};
int main()
{
MyLinkedList linkedList;
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); //链表变为1-> 2-> 3
std::cout<<linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
std::cout<<linkedList.get(1);
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//递归法
class Solution {
public:
ListNode*traversal(ListNode*pre,ListNode*cur){
//递归终止条件
if(cur==nullptr) return pre;
ListNode*nex=cur->next;
cur->next=pre;
return traversal(cur,nex);
}
ListNode* reverseList(ListNode* head) {
return traversal(nullptr,head);
}
};
//迭代法
class Solution2 {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr)return head;
ListNode*cur=head;
ListNode*pre=nullptr;
while(cur){
ListNode*nex=cur->next;
cur->next=pre;
pre=cur;
cur=nex;
}
return pre;
}
};/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode*dum=new ListNode(0);
dum->next=head;
ListNode*cur=dum;
while(cur->next!=nullptr&&cur->next->next!=nullptr){
ListNode*n1=cur->next;
ListNode*n3=cur->next->next->next;
cur->next=cur->next->next;
cur->next->next=n1;
cur->next->next->next=n3;
cur=cur->next->next;
}
return dum->next;
}
};class Solution {
public:
int getLen(ListNode*head)
{
int len=0;
while(head)
{
head=head->next;
len++;
}
return len;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
//先创建一个以head为next的节点
ListNode*dum=new ListNode(0,head);
//然后创建一个cur,与dum相同,用来循环到倒数位置，然后删除节点
ListNode*cur=dum;
//计算链表长度
int len=getLen(head);//此时已经改变head链表的内容
//开始for循环到倒数位置
for(int i=1;i<=len-n;i++)
{
cur=cur->next;
}
//当上面循环结束，说明到达倒数数字前一位，此时进行删除操作
cur->next=cur->next->next;
//返回结果
return dum->next;
}
};
//快慢指针
class Solution2 {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode*dum=new ListNode(0);
dum->next=head;
ListNode* fast=dum;
ListNode* slow=dum;
n++;
while(n--&&fast!=nullptr){
fast=fast->next;
}
while(fast!=nullptr){
fast=fast->next;
slow=slow->next;
}
slow->next=slow->next->next;
return dum->next;
}
};采用归并排序的方法，自上而下，时间复杂度nlogn，空间复杂度logn
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//自顶向下的归并排序
class Solution {
public:
ListNode* sortList(ListNode* head) {
//结束条件
if(head==nullptr||head->next==nullptr){
return head;
}
//寻找链表中间节点，使用快慢指针
ListNode*slow=head,*fast=head->next;
while(fast!=nullptr&&fast->next!=nullptr){
slow=slow->next;
fast=fast->next->next;
}
ListNode*mid=slow->next;
//将链表从中间断开
slow->next=nullptr;
ListNode*l1= sortList(head);
ListNode*l2= sortList(mid);
return merge(l1,l2);
}
ListNode* merge(ListNode*l1,ListNode*l2){
ListNode*dum=new ListNode(0);
ListNode*t=dum;
ListNode*t1=l1;
ListNode*t2=l2;
while(t1&&t2){
if(t1->val<=t2->val){
t->next=t1;
t1=t1->next;
}else{
t->next=t2;
t2=t2->next;
}
t=t->next;
}
if(t1){
t->next=t1;
}
if(t2){
t->next=t2;
}
return dum->next;
}
};/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode*dum=new ListNode(0,head);
ListNode*cur=dum;
//寻找left节点
for(int i=1;i<left;i++){
cur=cur->next;
}
ListNode*pre=cur;
cur=cur->next;
ListNode*nex=new ListNode;
//反转中间部分
for(int i=0;i<right-left;i++){
nex=cur->next;
cur->next=nex->next;
nex->next=pre->next;;
pre->next=nex;
}
return dum->next;
}
};问题描述：有两个由小到大的链表，把他们合并，并由小到大排序
解题思路：两个链表L1：1->3->6和L2：5->7，首先比较1和5，1小，排在5前，然后，比较3和5，3小，排在5前，接着比较6和5，5小，排在6前，然后比较6和7，6小，排在7前，一直在比较，属于递归问题。
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(list1==nullptr)
{
return list2;
}
if(list2==nullptr)
{
return list1;
}
if(list1->val<list2->val)
{
list1->next=mergeTwoLists(list1->next,list2);
return list1;
}
else
{
list2->next=mergeTwoLists(list2->next,list1);
return list2;
}
}
};
class Solution2 {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1||!list2){
return list1?list1:list2;
}
ListNode head,*tail=&head,*l1=list1,*l2=list2;
while(l1&&l2){
if(l1->val<l2->val){
tail->next=l1; l1=l1->next;
}else{
tail->next=l2; l2=l2->next;
}
tail=tail->next;
}
tail->next=l1?l1:l2;
return head.next;
}
};/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoList(ListNode*a,ListNode*b){
if(!a||!b)return a?a:b;
ListNode head,*tail=&head,*a1=a,*b1=b;
while(a1&&b1){
if(a1->val<b1->val){
tail->next=a1;a1=a1->next;
}else{
tail->next=b1;b1=b1->next;
}
tail=tail->next;
}
tail->next=(a1?a1:b1);
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode*ans=nullptr;
for(int i=0;i<lists.size();i++){
ans=mergeTwoList(ans,lists[i]);
}
return ans;
}
};给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
//如果首位是要删除的值，则直接返回下一个节点
if(head->val==val) return head->next;
ListNode*pre=head;
ListNode*cur=head->next;
while(cur!=NULL&&cur->val!=val){//把cur移动到要删除的位置
pre=cur;
cur=cur->next;
}
if(cur!=NULL) pre->next=cur->next;
return head;
}
};
class Solution2 {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
//获取链表长度
int n=0;
ListNode*temp=head;
while(temp){
n++;
temp=temp->next;
}
for(int i=0;n-i>k;i++){
head=head->next;
}
return head;
}
};
//快慢指针法
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
//首先让快指针移动k步
ListNode*fast=head;
ListNode*slow=head;
while(fast&&k>0){
fast=fast->next;
k--;
}
//将快慢指针同时后移，直到fast到末尾
while(fast){
fast=fast->next;
slow=slow->next;
}
return slow;
}
};class Solution {
public:
bool hasCycle(ListNode *head) {
set<ListNode*>st;
while(head){
if(st.count(head)){
return true;
}else{
st.insert(head);
}
head=head->next;
}
return false;
}
};class Solution1 {
public:
ListNode *detectCycle(ListNode *head) {
set<ListNode*>st;
while(head){
if(st.count(head)){
return head;
}
st.insert(head);
head=head->next;
}
return nullptr;
}
};
class Solution { //快慢指针
public:
ListNode *detectCycle(ListNode *head) {
ListNode*fast=head,*slow=head;
while(fast){
slow=slow->next;
if(fast->next==nullptr){
return nullptr;
}
fast=fast->next->next;
if(fast==slow){
ListNode*ptr=head;
while(ptr!=slow){
ptr=ptr->next;
slow=slow->next;
}
return ptr;
}
}
return nullptr;
}
};//创建和添加都没有返回值，所以都是null,只有删除有返回值
class CQueue {
private:
stack<int>stack1;
stack<int>stack2;
public:
CQueue() {
}
void appendTail(int value) {
stack1.push(value);
}
int deleteHead() {
//如果栈1为空，说明没有要删除的，直接返回-1
if(stack1.empty()) return -1;
//如果stack1有值，则全部放入stack2中，再删除stack2的top元素
while(!stack1.empty()){
int t=stack1.top();
stack1.pop();
stack2.push(t);
}
//删除头部元素
int res=stack2.top();
stack2.pop();
//然后将剩余数值移回stack1
while(!stack2.empty()){
int t=stack2.top();
stack2.pop();
stack1.push(t);
}
//移回后返回删除的值
return res;
}
};class MinStack {
public:
stack<int>st;
stack<int>minSt;
/** initialize your data structure here. */
MinStack() {
minSt.push(INT_MAX);
}
void push(int x) {
st.push(x);
minSt.push(::min(x,minSt.top()));
}
void pop() {
st.pop();
minSt.pop();
}
int top() {
return st.top();
}
int min() {
return minSt.top();
}
};class Solution {
public:
int fib(int n) {
if(n<2) return n;
int l=0,m=0,r=1;
for(int i=2;i<=n;++i){
l=m;
m=r;
r=(l+m)%1000000007;
}
return r;
}
};一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
第n阶台阶的跳法=[n-1]+[n-2]
class Solution {
public:
int numWays(int n) {
if(n<2) return 1;
int l=1,m=1,r=1;
for(int i=2;i<=n;i++){
l=m;
m=r;
r=(l+m)%1000000007;
}
return r;
}
};class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre=0;
int maxSum=nums[0];
for(auto x:nums){
pre=max(pre+x,x);
maxSum=max(maxSum,pre);
}
return maxSum;
}
};【剑指Offer最优解】 14- I. 剪绳子 I 又考我高中知识_哔哩哔哩_bilibili
class Solution {
public:
int cuttingRope(int n) {
if(n<=2) return 1;
if(n==3) return 2;
int res=n/3;
int mod=n%3;
int ans=0;
if(mod==0) ans=pow(3,res);
else if(mod==1) ans=pow(3,res-1)*4;
else if(mod==2) ans=pow(3,res)*2;
return ans;
}
};【剑指 Offer最优解】 47. 礼物的最大价值 ｜ 动态规划从二维优化成一维_哔哩哔哩_bilibili
class Solution {
public:
int maxValue(vector<vector<int>>& grid) {
int m=grid.size();
int n=grid[0].size();
if(grid.size()==0||grid[0].size()==0) return 0;
vector<vector<int>>dp(m,vector<int>(n));
dp[0][0]=grid[0][0];
for(int i=1;i<m;i++){ //左边界
dp[i][0]=dp[i-1][0]+grid[i][0];
}
for(int j=1;j<n;j++){ //上边界
dp[0][j]=dp[0][j-1]+grid[0][j];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
};【剑指Offer最优解】 49. 丑数 ｜ 没想到我连个丑数都找不出_哔哩哔哩_bilibili
class Solution {
public:
int nthUglyNumber(int n) {
vector<int>dp(n+1);
dp[1]=1;
int a=1,b=1,c=1;
for(int i=2;i<=n;i++){
dp[i]=min(min(dp[a]*2,dp[b]*3),dp[c]*5);
if(dp[i]==dp[a]*2) a++;
if(dp[i]==dp[b]*3) b++;
if(dp[i]==dp[c]*5) c++;
}
return dp[n];
}
};【剑指Offer最优解】 60. n个骰子的点数 ｜ 没想到这都能用动态规划_哔哩哔哩_bilibili
class Solution {
public:
vector<double> dicesProbability(int n) {
//使用二维数组存储 dp[i][j]表示i个色子，j种组合
vector<vector<int>>dp(n+1,vector<int>(6*n+1,0));
//当只有一个色子时，每种组合数为1
for(int i=1;i<=6;i++){
dp[1][i]=1;
}
//其他情况时
for(int i=2;i<=n;i++){ //色子数
for(int j=i;j<=6*i;j++){ //组合数
for(int k=1;k<=6;k++){
if(j<=k) break; //组合数为0不考虑
dp[i][j]+=dp[i-1][j-k];
}
}
}
//计算结果集合并返回
vector<double> ans(5*n+1);
int index=0;
int sum=pow(6,n);
for(int i=n;i<=6*n;i++){
ans[index++]=(double)dp[n][i]/sum;
}
return ans;
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans=0;
int n=prices.size();
if(n<=1) return 0;
int minVal=prices[0];
for(auto x:prices){
ans=max(ans,x-minVal);
minVal=min(minVal,x);
}
return ans;
}
};学长带你刷LeetCode第309题最佳买卖股票时机含冷冻期_哔哩哔哩_bilibili
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n=prices.size();
if(n==0) return 0;
vector<vector<int>>dp(n,vector<int>(3));
dp[0][0]=-prices[0]; //第一天买入，持有最大收益为负值
//dp[i][0] 第i天持有股票的最大收益,说明第i天买入了，或者昨天就买入了
//dp[i][1] 第i天不持有股票，且处于冷冻期，说明昨天持有，第i天刚卖
//dp[i][2] 第i天不持有股票，且不在冷冻期，说明昨天是冷冻期或者昨天就是非冷冻期
for(int i=1;i<n;i++){
dp[i][0]=max(dp[i-1][2]-prices[i],dp[i-1][0]);
dp[i][1]=dp[i-1][0]+prices[i];
dp[i][2]=max(dp[i-1][1],dp[i-1][2]);
}
return max(dp[n-1][1],dp[n-1][2]);
}
};class Solution1 {
public:
vector<int> exchange(vector<int>& nums) {
vector<int>res;
for(auto &x:nums)
if(x%2==1) res.push_back(x);
for(auto &x:nums)
if(x%2==0) res.push_back(x);
return res;
}
};
//双指针法
class Solution {
public:
vector<int> exchange(vector<int>& nums) {
int n=nums.size();
vector<int>res(n);
int l=0,r=n-1;
for(auto &x:nums){
if(x%2==1){
res[l++]=x;
}
else{
res[r--]=x;
}
}
return res;
}
};Leetcode 581. 最短无序连续子数组 排序_哔哩哔哩_bilibili
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
vector<int>v=nums;
sort(v.begin(),v.end());
int l=-1;
int r=-1;
for(int i=0;i<v.size();i++){
if(nums[i]!=v[i]){
l=i;
break;
}
}
for(int j=v.size()-1;j>=0;j--){
if(nums[j]!=v[j]){
r=j;
break;
}
}
if(l==-1||r==-1) return 0;
return r-l+1;
}
};class Solution1 {
public:
int hammingWeight(uint32_t n) {
int res=0;
while(n!=0){
res+=n&1;//计算最右边的一位是否为1
n>>=1;//右移一位
}
return res;
}
};
class Solution {
public:
int hammingWeight(uint32_t n) {
int res=0;
while(n!=0){
res++;
n&=(n-1);//每次n&(n-1)会消除一个1
}
return res;
}
};class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
//使用哈希表
unordered_map<int,int>mp;
for(int i=0;i<nums.size();i++){
unordered_map<int,int>::iterator it=mp.find(target-nums[i]);
if(it!=mp.end()){//如果找到了
return {it->second,i};
}
//如果找不到，则加入哈希表中
mp[nums[i]]=i;
}
return {};
}
};class Solution {
public:
unordered_map<char,char>mp{
{')','('},
{'}','{'},
{']','['}
};
bool isValid(string s) {
stack<char>st;
for(int i=0;i<s.size();i++){
if(mp.count(s[i])){//如果找到匹配的括号
if(st.empty()||st.top()!=mp[s[i]]){ //如果栈顶元素不能与当前元素组成括号，直接返回false
return false;
}
st.pop();//否则出栈
}else{//找不到则压入栈
st.push(s[i]);
}
}
return st.empty();
}
};Leetcode 560 和为 K 的子数组_哔哩哔哩_bilibili
使用暴力枚举，或者前缀和方法
class Solution1 { //枚举
public:
int subarraySum(vector<int>& nums, int k) {
int count=0;
for(int i=0;i<nums.size();i++){
int sum=0;
for(int j=i;j>=0;j--){
sum+=nums[j];
if(sum==k) count++;
}
}
return count;
}
};
class Solution { //哈希前缀和
public:
int subarraySum(vector<int>& nums, int k) {
int count=0;
int pre=0; //前缀和
unordered_map<int,int>mp;
mp[0]=1; //恰好前缀和=0的为1个
for(auto x:nums){
pre+=x;
if(mp.count(pre-k)){
count+=mp[pre-k];
}
mp[pre]++;
}
return count;
}
};