双指针算法，是一种非常常见的 O(n) 时间复杂度的算法，也正因时间复杂度的优势常见于中等难度的算法题目中。
其特点为：两个下标通常为i和j 。
其算法又可细分为：相向型指针、背向型指针和同向型指针。
相向指针相向型双指针题目即：两个下标从两端往中间趋近。
-
判断回文串
bool isPalidrome(string s) { int l = 0, r = s.length() - 1; while(l < r) { if(s[l++] != s[r--]) return false; } return true; } -
两数之和
给定一个数组求对应元素之和为sum的两个元素的下标（双指针入门题目）。
pair
a, int sum) { sort(a.begin(), a.end()); int i = 0, j = a.size() - 1; pair
背向型指针即基于中心线向左右展开，与相向型指针刚好相反。最典型的题目是最长对称子串。
int longestPalidrome(string s)
{
int len = s.length(), max_l = 1, l, r, ans;
for(int i = 0; i < len; i++)
{
//串长为奇数
l = i - 1, r = i + 1, ans = 1;
while(l >= 0 && r < len && s[l--] == s[r++]) ans += 2;
max_l = max(max_l, ans);
//串长为偶数
l = i, r = i + 1, ans = 0;
while(l >= 0 && r < len && s[l--] == s[r++]) ans += 2;
max_l = max(max_l, ans);
}
return max_l;
}
同向指针
快慢指针在动态维护一个窗口
标签：动态解窗口 连续子段 最短最长
-
剑指Offer II 008. 和大于等于 target 的最短子数组
题意描述：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和≥target的长度最小的连续子数组返回其长度。如果不存在符合条件的子数组，返回 0 。
int minSubArrayLen(int target, vector
nums) { int l = 0, r = 0, len = INT_MAX, n = nums.size(); int sum = 0; while(l <= r && l < n) { while(r < n && sum < target){ sum += nums[r++]; } if(sum >= target) len = min(len, r - l); sum -= nums[l++]; } if(len == INT_MAX) return 0; return len; } -
1375 · 至少K个不同字符的子串
题意描述：给定一个仅包含小写字母的字符串 S。返回 S 中至少包含 k 个不同字符的子串的数量。
long long kDistinctCharacters(string s, int k) { int l = 0, r = 0, sum = 0, index; int n = s.length(), cnt[26] = {0}; long long ans = 0; while(l <= r && l < n) { // 统计当前不同的字符数 while(r < n && sum != k) { index = s[r++] - 'a'; if(!cnt[index]) sum++; cnt[index]++; } //统计字串个数 if(sum == k) ans += n - r + 1; index = s[l++] - 'a'; cnt[index]--; if(!cnt[index]) sum--; } return ans; } -
剑指 Offer 48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
int lengthOfLongestSubstring(string s) { int l = 0, r = 0, n = s.length(), cnt[300] = {0}, ind = 0; int ans = 0; while(l <= r && l < n) { while(r < n){ ind = s[r]; if(cnt[ind]) break; cnt[ind]++; r++; } ans = max(ans, r - l); ind = s[l++]; cnt[ind]--; } return ans; } -
386 · 最多有k个不同字符的最长子字符串
题意描述：给定字符串S，找到最多有k个不同字符的最长子串T。
int lengthOfLongestSubstringKDistinct(string s, int k) { int l = 0, r = 0, n = s.length(), sum = 0, indx = 0; int cnt[300] = {0}, ans = 0; while(l <= r && l < n) { while(r < n && sum <= k) { indx = s[r++]; if(!cnt[indx]) sum++; cnt[indx]++; } if(sum > k) ans = max(ans, r - l -1); else ans = max(ans, r - l); indx = s[l++]; cnt[indx]--; if(!cnt[indx]) sum--; } return ans; } -
leet code 76. 最小覆盖子串
提议描述：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。注意t中字符可能重复，要求字符种类及个数均被涵盖。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
// 判断是否个数和种类完全覆盖 bool check(set
&s, int cnt_t[], int cnt_sub[]) { for(auto item : s) { if(cnt_sub[item] < cnt_t[item]) return 0; } return 1; } string minWindow(string s, string t) { set set_t(t.begin(), t.end()); int l = 0, r = 0, ans = INT_MAX, n = s.length(), indx; int cnt_t[300] = {0}, cnt_sub[300] = {0}; //统计t串字符 for(auto item : t) cnt_t[item]++; string str = ""; while(l <= r && l < n) { // 维护了一个包含t中所有字符的子串 while(r < n && !check(set_t, cnt_t, cnt_sub) ) { indx = r++; cnt_sub[s[indx]]++; } if(check(set_t, cnt_t, cnt_sub) && r - l < ans) { ans = r - l; str = s.substr(r - ans, ans); } indx = l++; cnt_sub[s[indx]]--; } return str; }
