数组删除元素的原理，并不是真正意义的删除，而是将需要删除的元素用其它元素覆盖，时间复杂度为
- 链接https://leetcode.cn/problems/remove-element/
- 解题思路：双指针
新指针 k 用来存新数组的下标
旧指针 i 用来遍历原来的数组
元素存入新数组条件：只要原数组中的元素不是要删除的元素都要存入新数组 - leetcode解题代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for (int i = 0; i < nums.size(); i ++){
if (nums[i] != val)
nums[k ++] = nums[i];
}
return k;
}
};
- 链接https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
- 解题思路：双指针
新指针 k 用来存新数组的下标
旧指针 i 用来遍历原来的数组
元素存入新数组条件：第一个元素要存入新数组，从第二个元素开始，所有和上一个元素不相等的元素都要存入新数组 - leetcode解题代码
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0;
for (int i = 0; i < nums.size(); i ++){
if (i == 0 || nums[i] != nums[i - 1])
nums[k ++] = nums[i];
}
return k;
}
};
- 链接https://leetcode.cn/problems/move-zeroes/
- 解题思路：双指针
新指针 k 用来存新数组的下标
旧指针 i 用来遍历原来的数组
元素存入新数组条件：只要原数组中的元素不是 0，就存入新数组
将新数组其余的位赋值为 0 即可 - leetcode解题代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int k = 0;
for (int i = 0; i < nums.size(); i ++){
if (nums[i] != 0)
nums[k ++] = nums[i];
}
while (k < nums.size()) nums[k ++] = 0;
}
};
- 链接https://leetcode.cn/problems/backspace-string-compare/
- 解题思路：双指针
新指针 k 用来存新数组的下标
旧指针 i 用来遍历原来的数组
元素存入新数组条件：只要原数组中的元素不是 #，就存入新数组，如果是 #，就将新数组的下标前移一位（新数组的下标大于 0）
resize 函数调整新数组的尺寸 - leetcode解题代码
class Solution {
public:
void get(string &s){
int k = 0;
for (int i = 0; i < s.size(); i ++){
if (s[i] != '#')
s[k ++] = s[i];
else
if (k > 0)
k --;
}
s.resize(k);
}
bool backspaceCompare(string s, string t) {
get(s);
get(t);
return s == t;
}
};
- 链接https://leetcode.cn/problems/squares-of-a-sorted-array/
- 解题思路：双指针
- 注意：由于数组是有序的，最大值只可能出现在原来数组的两端，所以新数组也从最末端开始存
新指针 k 用来存新数组的下标
旧指针 i j 用来遍历原来的数组，i 从前往后遍历，j 从后往前遍历
元素存入新数组条件：比较下标 i 和下标 j 元素的平方，新数组存较大的那个值 - leetcode解题代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> res(n);
for (int i = 0, j = n - 1, k = n - 1; i <= j;){
if (nums[i] * nums[i] > nums[j] * nums[j]){
res[k] = nums[i] * nums[i];
k --, i ++;
}
else {
res[k] = nums[j] * nums[j];
k --, j --;
}
}
return res;
}
};
- 链接https://leetcode.cn/problems/3sum/
- 解题思路：双指针
- 注意：将数组排序用于去重和指针移动
指针 i l r 分别用于找三个符合要求的元素
i 遍历原数组
当 i 遍历原数组的时候定义 l 和 r，l 位于 i 的右侧 r 位于数组末尾
当三数之和大于 0 则 r 指针向前移动
小于 0 则 l 指针向后移动
等于 0 输出答案数组，并且 l 向后移动同时 r 向前移动，同时 l 和 r也需要进行去重操作 - 难点：三个指针都需要进行去重操作，注意边界条件
- leetcode解题代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> res;
for (int i = 0; i < n; i ++){
// 对 i 指针去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = n - 1;
while (l < r){
if (nums[i] + nums[l] + nums[r] > 0) r --;
else if (nums[i] + nums[l] + nums[r] < 0) l ++;
else {
res.push_back({nums[i], nums[l], nums[r]});
// 对 l，r 指针去重
while (l < r && nums[l] == nums[l + 1]) l ++;
while (l < r && nums[r] == nums[r - 1]) r --;
l ++, r --;
}
}
}
return res;
}
};
- 链接https://leetcode.cn/problems/4sum/
- 解题思路：双指针
和上一题类似，多加一个 for 循环多一重判断 - leetcode解题代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int k = 0; k < n; k ++){
if (k > 0 && nums[k] == nums[k - 1]) continue;
for (int i = k + 1; i < n; i ++){
if (i > k + 1 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = n - 1;
while (l < r){
if ((long)nums[k] + nums[i] + nums[l] + nums[r] > target) r --;
else if ((long)nums[k] + nums[i] + nums[l] + nums[r] < target) l ++;
else {
res.push_back({nums[k], nums[i], nums[l], nums[r]});
while (l < r && nums[l] == nums[l + 1]) l ++;
while (l < r && nums[r] == nums[r - 1]) r --;
l ++, r --;
}
}
}
}
return res;
}
};
- 链接https://leetcode.cn/problems/minimum-size-subarray-sum/
- 解题思路：双指针(滑动窗口)
i 指针用来遍历原数组，k 指针用来更新窗口大小
当窗口内元素总和大于目标值，尝试删除 k 指针的元素，如果删除 k 指针的元素总和依然大于目标值，那么 k 指针向后移动，直到无法删除k 指针的元素，更新窗口内的最少元素个数 - leetcode解题代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0, res = INT_MAX;
int k = 0;
for (int i = 0; i < nums.size(); i ++){
sum += nums[i];
while (sum - nums[k] >= target){
sum -= nums[k];
k ++;
}
if (sum >= target) res = min(res, i - k + 1);
}
if (res == INT_MAX) return 0;
return res;
}
};
- 链接https://leetcode.cn/problems/fruit-into-baskets/
- 解题思路：双指针(滑动窗口) + 哈希表
i 指针用来遍历原数组，k 指针用来更新窗口大小
题目要求不能采摘超过两种水果，所以需要用哈希表记录水果出现的次数，type 表示水果的种类，当水果出现的次数为 0，则水果种类需要 -1
当水果种类大于 2，则窗口大小需要更新 - leetcode解题代码
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int res = 0, type = 0;
unordered_map<int, int> cnt;
int k = 0;
for (int i = 0; i < fruits.size(); i ++){
cnt[fruits[i]] ++;
if (cnt[fruits[i]] == 1) type ++;// 如果字符第一次出现说明是一种新的水果
while (type > 2){
cnt[fruits[k]] --;
if (cnt[fruits[k]] == 0) type --;// 如果字符删除之后出现的次数为 0，说明少了一种水果
k ++;
}
res = max(res, i - k + 1);
}
return res;
}
};
- 链接https://leetcode.cn/problems/longest-substring-without-repeating-characters/
- 解题思路：双指针(滑动窗口)
i 指针用来遍历原数组，k 指针用来更新窗口大小
题目要求不能有重复字符，所以需要用哈希表记录字符出现的次数，当字符出现的次数大于 1，则移动 k 指针更新窗口大小 - leetcode解题代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
unordered_map<char, int> hs;
int k = 0;
for (int i = 0; i < s.size(); i ++){
hs[s[i]] ++;
while (hs[s[i]] > 1){
hs[s[k]] --;
k ++;
}
res = max(res, i - k + 1);
}
return res;
}
};
- 链接https://leetcode.cn/problems/minimum-window-substring/
- 解题思路：双指针(滑动窗口)
i 指针用来遍历原数组，k 指针用来更新窗口大小
题目要求找到覆盖 t 的最小子串，所以需要用哈希表记录子串 t 中每个字符出现的次数，同时记录 s 中每个字符出现的次数
当 s 中每个字符出现的次数小于等于 t 中字符出现的次数，说明当前字符是有效的，当 s 中字符出现的次数大于 t 中字符出现的次数，说明需要更新窗口大小
当有效字符数量和子串 t 中字符数量相等，则更新答案 - leetcode解题代码
class Solution {
public:
string minWindow(string s, string t) {
string res;
int cnt = 0;// 有效字符的数量
unordered_map<char, int> hs, ht;
for (auto c: t) ht[c] ++;
int k = 0;
for (int i = 0; i < s.size(); i ++){
hs[s[i]] ++;
if (hs[s[i]] <= ht[s[i]]) cnt ++;// 是一个有效字符
while (hs[s[k]] > ht[s[k]]){
hs[s[k]] --;
k ++;
}
if (cnt == t.size()){
if (res.empty() || i - k + 1 < res.size())
res = s.substr(k, i - k + 1);
}
}
return res;
}
};
- 链接https://leetcode.cn/problems/permutation-in-string/
- 解题方法：哈希表 + 滑动窗口
i 指针用来遍历原数组，k 指针用来更新窗口大小
题目要求找到s2 是否包含 s1 的排列，与上一题不同之处在于不能有其它的字符
用哈希表记录子串 s1 中每个字符出现的次数，同时记录 s2 中每个字符出现的次数
与上一题区别在于，字符出现的次数需要完全相等，所以在指针移动之前需要更新有效字符的数量 - leetcode解题代码
class Solution {
public:
unordered_map<char, int> h1, h2;
bool check(char c){
if (h1.count(c) && h1[c] == h2[c])
return true;
return false;
}
bool checkInclusion(string s1, string s2) {
for (auto c: s1) h1[c] ++;
int cnt = 0;// 有多少个字符满足要求
int k = 0;// 滑动窗口左端点
for (int i = 0; i < s2.size(); i ++){
if (check(s2[i])) cnt --;// 如果当前字符满足要求，添加一个字符就会使其不满足要求
h2[s2[i]] ++;
if (check(s2[i])) cnt ++;
// 当窗口大小大于短串的长度，右端点开始移动
if (i - k + 1 > s1.size()){
if (check(s2[k])) cnt --;
h2[s2[k]] --;
if (check(s2[k])) cnt ++;
k ++;
}
if (cnt == h1.size()) return true;
}
return false;
}
};
- 链接https://leetcode.cn/problems/find-all-anagrams-in-a-string/
- 解题方法：哈希表 + 滑动窗口
和上一题类似 - leetcode解题代码
class Solution {
public:
unordered_map<char, int> hs, hp;
bool check(char c){
if (hs.count(c) && hs[c] == hp[c])
return true;
return false;
}
vector<int> findAnagrams(string s, string p) {
vector<int> res;
for (auto c: p) hp[c] ++;
int cnt = 0;// 有多少个字符满足要求
int k = 0;// 滑动窗口左端点
for (int i = 0; i < s.size(); i ++){
if (check(s[i])) cnt --;// 如果当前字符满足要求，添加一个字符就会使其不满足要求
hs[s[i]] ++;
if (check(s[i])) cnt ++;
// 当窗口大小大于短串的长度，右端点开始移动
if (i - k + 1 > p.size()){
if (check(s[k])) cnt --;
hs[s[k]] --;
if (check(s[k])) cnt ++;
k ++;
}
if (cnt == hp.size()) res.push_back(k);
}
return res;
}
};
- 链接https://leetcode.cn/problems/reverse-string/
- 解题思路：双指针
i 指针 j 指针分别指向字符串首尾两端，每次交换两个字符，交换完成之后两个指针都向中间移动一位 - leetcode解题代码
class Solution {
public:
void reverseString(vector<char>& s) {
int i = 0, j = s.size() - 1;
while (i < j){
swap(s[i], s[j]);
i ++, j --;
}
}
};
- 链接https://leetcode.cn/problems/reverse-string-ii/
- 解题方法：双指针
定义维护的区间 [l, r]，每次维护 2k 个数
如果区间不足 k 个数，r 指针指向区间结尾
如果区间超过 k 个数，r 指针指向区间第 k 个数 - leetcode解题代码
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.size();
for (int i = 0; i < n - 1; i += k * 2){
int l = i, r = min(i + k, n);
reverse(s.begin() + l, s.begin() + r);
}
return s;
}
};
- 链接https://leetcode.cn/problems/reverse-words-in-a-string-iii/
- 解题思路：双指针
i 指针用来找每个单词的首位两个字符的下标，k 指针用来找每个单词中间的空格
当 k 遍历到空格时，说明找到了一个完整的单词，反转 i k 指针之间的单词 - leetcode解题代码
class Solution {
public:
string reverseWords(string s) {
for (int i = 0; i < s.size(); i ++){
int k = i;
while (k < s.size() && s[k] != ' ') k ++;
reverse(s.begin() + i, s.begin() + k); // reverse区间[)左闭右开
i = k;
}
return s;
}
};
- 链接https://leetcode.cn/problems/reverse-words-in-a-string/
- 解题思路：双指针
反转字符串中的单词：反转整个字符串的顺序 + 反转每个单词的顺序
需要去除前导和尾随空格，还要去除每个单词中间多余的空格 - leetcode解题代码
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end());
while (s.back() == ' ') s.pop_back();
reverse(s.begin(), s.end());
while (s.back() == ' ') s.pop_back();
reverse(s.begin(), s.end());
for (int i = 0; i < s.size(); i ++){
int k = i;
while (k < s.size() && s[k] != ' ') k ++;
reverse(s.begin() + i, s.begin() + k);
while (k < s.size() && s[k + 1] == ' ') s.erase(s.begin() + k);
i = k;
}
return s;
}
};
- 链接https://leetcode.cn/problems/remove-linked-list-elements/
- 解题方法：双指针
cur 指针指向新链表的最后一个节点
p 指针从 head 开始遍历链表，如果 p 指针元素不是要删除的元素则将 cur 指针指向 p，并更新 cur 指针
最后 cur 指针是无重复元素链表的最后一个节点，要将其指向空 - leetcode解题代码
/**
* 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* removeElements(ListNode* head, int val) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto cur = dummy;
for (auto p = head; p; p = p->next){
if (p->val != val)
cur = cur->next = p;
}
cur->next = nullptr;
return dummy->next;
}
};
- 链接https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
- 解题方法：双指针
cur 指针指向无重复元素链表的最后一个节点
p 指针从 head->next 开始遍历链表（第一个节点一定添加到新链表中），如果 p 指针元素和 cur 指针元素不相等则将 cur 指针指向 p，并更新 cur 指针
最后 cur 指针是无重复元素链表的最后一个节点，记得将其指向空 - leetcode解题代码
/**
* 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* deleteDuplicates(ListNode* head) {
if (!head) return head;
auto cur = head;
for (auto p = head->next; p; p = p->next)
if (p->val != cur->val)
cur = cur->next = p;
cur->next = nullptr;
return head;
}
};
- 链接https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/submissions/
- 解题方法：双指针
cur 指针维护新链表的最后一位，next 指针遍历去找无重复元素的区间
如果区间长度 =1 则说明没有重复元素，保留
如果区间长度 >1 则说明有重复元素，删除整个区间 - leetcode解题代码
/**
* 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* deleteDuplicates(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto cur = dummy;
while (cur->next){
auto next = cur->next;
while (next && cur->next->val == next->val) next = next->next;
if (next == cur->next->next) cur = cur->next;
else cur->next = next;
}
return dummy->next;
}
};
- 链接https://leetcode.cn/problems/reverse-linked-list/
- 解题思路：双指针
a 指向第一个节点，b 指向第二个节点
当第二个节点存在时，每次将第二个节点的指针指向第一个节点，并且将 a 指针和 b 指针都向后移动一位，最后将头节点指向空 - leetcode解题代码
/**
* 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* reverseList(ListNode* head) {
if (!head) return nullptr;
auto a = head, b = head->next;
while (b){
auto c = b->next;
b->next = a;
a = b, b = c;
}
head->next = nullptr;
return a;
}
};
- 链接https://leetcode.cn/problems/reverse-linked-list-ii/
- 解题方法：双指针
找到 [L, R] 区间的第 L-1 个节点
将 [L, R] 区间反转
将反转后的链表与原链表连接 - leetcode解题代码
/**
* 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) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
for (int i = 0; i < left - 1; i ++) p = p->next;
auto a = p->next, b = a->next;
for (int i = 0; i < right - left; i ++){
auto c = b->next;
b->next = a;
a = b, b = c;
}
p->next->next = b;
p->next = a;
return dummy->next;
}
};
- 链接https://leetcode.cn/problems/intersection-of-two-linked-lists/
- 解题思路：双指针
a链表长度 + 公共长度 + b链表长度 = b链表长度 + 公共长度 + a链表长度
a 指向第一个链表的头节点，b 指向第二个链表的头节点，当 a 指针和 b 指针未相遇时，a 和 b 都向后移动，当 a 指向空了，将其指向第二个链表的头节点，同理当 b 指向空了，将其指向第一个链表的头节点，一定会在相交节点相遇 - leetcode解题代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto a = headA, b = headB;
while (a != b){
if (a) a = a->next;
else a = headB;
if (b) b = b->next;
else b = headA;
}
return a;
}
};
- 链接https://leetcode.cn/problems/middle-of-the-linked-list/
- 解题思路：双指针
快指针每次移动两位，慢指针每次移动一位，当快指针指向链表末尾，慢指针刚好指向链表的中间节点 - 注意：题目要求如果有两个中间节点，则返回第二个中间节点，如果要求返回第一个中间节点，代码需要改成
while (f && f->next && f->next->next) - leetcode解题代码
/**
* 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* middleNode(ListNode* head) {
auto f = head, s = head;
while (f && f->next){
s = s->next, f = f->next->next;
}
return s;
}
};
- 链接https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/
- 解题思路：双指针
快指针每次移动两位，慢指针每次移动一位，当快指针指向链表末尾，慢指针刚好指向链表的中间节点
由于我们需要找到中间节点的前驱节点，所以将快慢指针都前移一位到虚拟头节点，当快指针指向链表末尾，慢指针刚好指向链表中间节点的前驱节点 - leetcode解题代码
/**
* 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* deleteMiddle(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto f = dummy, s = dummy;
while (f && f->next && f->next->next){
s = s->next, f = f->next->next;
}
s->next = s->next->next;
return dummy->next;
}
};
- 链接https://leetcode.cn/problems/linked-list-cycle/
- 解题思路：双指针
快指针每次移动两位，慢指针每次移动一位，如果存在环，则一定会相交，否则不存在环 - leetcode解题代码
class Solution {
public:
bool hasCycle(ListNode *head) {
auto fast = head, slow = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
};
- 链接https://leetcode.cn/problems/linked-list-cycle-ii/
- 解题思路：双指针
判断是否有环和上一题相同，当两个指针相遇时，将其中一个指针指向链表头节点，另一个指针的位置不变，将快指针和慢指针都改为每次移动一位，当两个节点再次相遇时，就是环的入口节点，数学证明略 - leetcode解题代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (!head || !head->next) return NULL;
auto slow = head, fast = head;
while (fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if (slow == fast){
slow = head;
while (slow != fast){
slow = slow->next;
fast = fast->next;
}
return slow;
}
}
return NULL;
}
};