-
二分法
- 按左闭右闭的区间处理
-
- 适合已经完成排序的，找target数——减少暴力遍历
元素移动类题目
两种方法：
1、双指针
移动规则不同：
移动条件不同\fast一次跳两步，slow一次一步
适合解决元素移动/排序/查找
链表中找环
fast在后面遍历每一个数，slow在需要插入位置
只有在需要插入的时候，fast赋值到slow，且slow向前移动
格式：for（fast遍历每个元素）
if（需要插入）fast->slow；slow++
27. 移除元素
力扣题目链接(opens new window)
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
int removeElement(int* nums, int numsSize, int val) {int k=0;for (int i=0;i<numsSize;i++){if(nums[i]!=val){nums[k]=nums[i];k++;}}return k;
}977.有序数组的平方
力扣题目链接(opens new window)
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
- 输入：nums = [-4,-1,0,3,10]
- 输出：[0,1,9,16,100]
- 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
分析：因为最大值肯定在最左\最右侧，可以通过双指针+创建新的数组空间得到答案
2、直接遍历
关键：注意遍历方向，减少移动的次数——优先从后往前遍历
eg：从前往后遍历，一个需要删除，那么后面的都需要移动
3、向左右移动k个元素
reverse三次
子串类题目
1、滑动窗口（其实是一种双指针）
是对暴力循环子串开头和结尾的优化
按照某个条件——不断的调节子序列的起始位置和终止位置——得出我们要想的结果
通常模式：
for 对于正在考虑的元素i
如果不符合条件了，就出队前元素 直至符合条件
实际上任何条件都可以进队
每次符合条件，都构成一个输出
**涉及到子串的字母构成，会用到哈希表
209.长度最小的子数组
力扣题目链接(opens new window)
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
- 输入：s = 7, nums = [2,3,1,2,4,3]
- 输出：2
- 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
int minSubArrayLen(int target, int* nums, int numsSize) {int l=0,r=0,sum=nums[0];int ansmin=INT_MAX;if(sum>=target) return 1;while(r+1<numsSize){r++;sum+=nums[r];if(sum>=target){ansmin = fmin(ansmin,r-l+1);}while(sum - nums[l]>=target){sum-=nums[l];l++;ansmin=fmin(ansmin,r-l+1);}}if(ansmin==INT_MAX) return 0;return ansmin;
}2、接雨水类题目
1、单调栈
2、双指针
一块地方能接多少雨水，取决于左边/右边的第一个更大值
先通过双指针 遍历得到 每块左边/右边第一个更大值
这块能累计的雨水 = fmin（左边，右边）-本块高度
3、贪心算法
-连续子串的和 要求最大
和大于0才能往下走，小于0丢掉
-贪心算法 来解决 几个区间重合的问题
二维矩阵
搜索可以用排除法
字符串
典型题目：reverse
典型题目：KMP