class Solution {
public:
vector twoSum(vector& nums, int target) {
unordered_mapm;
int n=nums.size();
for(int i=0;i
26：删除有序数组中的重复项-力扣
class Solution {
public:
int removeDuplicates(vector& nums) {
int n=nums.size();
for(auto it=nums.begin();it!=nums.end();){
if(it!=nums.begin() && *it==*(it-1)){
nums.erase(it);
}else{
++it;
}
}
return nums.size();
}
};
27：移除元素-力扣
class Solution {
public:
int removeElement(vector& nums, int val) {
for(auto it=nums.begin();it!=nums.end();){
if(*it==val){
nums.erase(it);
}else{
++it;
}
}
return nums.size();
}
};
283. 移动零 - 力扣（LeetCode）
也可用双指针，类似于冒泡思想
class Solution {
public:
void moveZeroes(vector& nums) {
int i=0;
for(auto it=nums.begin();it!=nums.end(),i
2.动态规划（Easy）
53.最大子数组和-力扣
class Solution {
public:
int maxSubArray(vector& nums) {
int pre=0;
int maxAns=nums[0];
for(auto &i:nums){
pre=max(pre+i,i);
maxAns=max(maxAns,pre);
}
return maxAns;
}
};
746. 使用最小花费爬楼梯 - 力扣（LeetCode）
class Solution {
public:
int minCostClimbingStairs(vector& cost) {
int n=cost.size();
vectordp(n+1);
dp[0]=dp[1]=0;
for(int i=2;i<=n;++i){
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[n];
}
};
3.二分查找
704. 二分查找 - 力扣（LeetCode）
class Solution {
public:
int search(vector& nums, int target) {
int left=0,right=nums.size()-1;
while(left<=right){
int mid=left+(right-left)/2;
if(nums[mid]==target){
return mid;
}else if(nums[mid]
剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode）
此题也可用deque来做
class Solution {
public:
int minArray(vector& numbers) {
if(numbers.size()==0)return 0;
int left=0,right=numbers.size()-1;
while(leftnumbers[right]){
left=mid+1;
}else if(numbers[mid]==numbers[right]){
--right;
}else{
right=mid;
}
}
return numbers[left];
}
};
4.哈希表(unordered_map,unordered_set)
217. 存在重复元素 - 力扣（LeetCode）
class Solution {
public:
bool containsDuplicate(vector& nums) {
unordered_mapm;
for(auto &i:nums){
if(m.count(i)){
return true;
}
m[i]++;
}
return false;
}
};
219. 存在重复元素 II - 力扣（LeetCode）
与上一题差不多，只不过添加了一些约束
class Solution {
public:
bool containsNearbyDuplicate(vector& nums, int k) {
int n=nums.size();
unordered_mapm;
for(int i=0;i
5.数学
136. 只出现一次的数字 - 力扣（LeetCode）
异或
class Solution {
public:
int singleNumber(vector& nums) {
int ans=0;
for(auto &i:nums){
ans^=i;
}
return ans;
}
};
169. 多数元素 - 力扣（LeetCode）
摩尔投票法（拉帮结派）
class Solution {
public:
int majorityElement(vector& nums) {
int count=0;
int target=nums[0];
for(auto &i:nums){
if(count==0){
target=i;
}
if(i==target){
++count;
}else{
--count;
}
}
return target;
}
};
剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode）
异或
class Solution {
public:
int missingNumber(vector& nums) {
int res=0;
int n=nums.size();
for(int i=0;i
6.双指针
977. 有序数组的平方 - 力扣（LeetCode）
利用好数组升序的特性，确定正负交界，双指针操作类似于归并排序
class Solution {
public:
vector sortedSquares(vector& nums) {
int pivot=-1;
for(int i=0;ians;
int p1=pivot,p2=pivot+1;
while(p1>=0 && p2=0){
ans.emplace_back(nums[p1]*nums[p1]);
--p1;
}
while(p2
283. 移动零 - 力扣（LeetCode）
类似冒泡的思想
class Solution {
public:
void moveZeroes(vector& nums) {
int left=0,right=0;
while(right
350. 两个数组的交集 II - 力扣（LeetCode）
这里很巧妙，肯定是短的数组先到末尾，结束循环，&&而不是||
class Solution {
public:
vector intersect(vector& nums1, vector& nums2) {
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int p1=0,p2=0;
//4 5 9
//4 4 8 9 9
vectorans;
while(p1nums2[p2]){
p2++;
}else{
ans.emplace_back(nums1[p1]);
p1++;
p2++;
}
}
return ans;
}
};
7.滑动窗口
219. 存在重复元素 II - 力扣（LeetCode）
一种滑动窗口的实现方式，很值得学习一下
class Solution {
public:
bool containsNearbyDuplicate(vector& nums, int k) {
unordered_sets;
for(int i=0;ik){
s.erase(nums[i-k-1]);
}
if(s.count(nums[i])){
return true;
}
s.emplace(nums[i]);
}
return false;
}
};
。一些模板题
剑指 Offer 29. 顺时针打印矩阵 - 力扣（LeetCode）
class Solution {
public:
vector spiralOrder(vector>& matrix) {
if(matrix.empty())return {};
int left=0,right=matrix[0].size()-1;
int top=0,bottom=matrix.size()-1;
vectorans;
while(true){
for(int i=left;i<=right;++i){
ans.emplace_back(matrix[top][i]);
}
if(++top>bottom)break;
for(int i=top;i<=bottom;++i){
ans.emplace_back(matrix[i][right]);
}
if(--right=left;--i){
ans.emplace_back(matrix[bottom][i]);
}
if(--bottom=top;--i){
ans.emplace_back(matrix[i][left]);
}
if(++left>right)break;
}
return ans;
}
};
剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）
TopK问题， 优先队列（堆排序）
class Solution {
public:
vector getLeastNumbers(vector& arr, int k) {
priority_queue,greater<>>q;
vectorans;
for(auto &i:arr){
q.push(i);
}
for(int i=0;i
1984. 学生分数的最小差值 - 力扣（LeetCode）
最大值最小化， 排序往往是解决办法
class Solution {
public:
int minimumDifference(vector& nums, int k) {
sort(nums.begin(),nums.end());
int MIN=INT_MAX;
for(int i=0;i+k-1
