力扣大神写的诗
一开始不理解滑动窗口是什么!
看完此诗我才明白,滑动窗口其实就是双指针的一种形式
左右指针齐头进。
c#代码如下
public class Solution {public IList<int> FindAnagrams(string s, string p) {Dictionary<char, int> need = new Dictionary<char, int>();Dictionary<char, int> window = new Dictionary<char, int>();for (int i = 0; i < p.Length; i++){if (need.ContainsKey(p[i]))need[p[i]]++;elseneed.Add(p[i], 1);}int left = 0;int right = 0;int valid = 0;IList<int> res = new List<int>();while (right < s.Length){char c = s[right];right++;if (need.ContainsKey(c)){if (window.ContainsKey(c))window[c]++;elsewindow.Add(c, 1);if (window[c] == need[c])valid++;}while (right - left >= p.Length){if (valid == need.Count){res.Add(left);}char d = s[left];left++;if (need.ContainsKey(d)){if (window[d] == need[d])valid--;window[d]--;}}}return res;}}
c#代码 用双指针解决上面问题
public class Solution {public bool BackspaceCompare(string s, string t) {int sRight = s.Length - 1;int tRight = t.Length - 1;int skipS = 0;int skipT = 0;while (sRight >= 0 || tRight >= 0){while (sRight >= 0){if (s[sRight] == '#'){skipS++;sRight--;}else if (skipS > 0){skipS--;sRight--;}elsebreak;}while (tRight >= 0){if (t[tRight] == '#'){skipT++;tRight--;}else if (skipT > 0){skipT--;tRight--;}elsebreak;}if (sRight >= 0 && tRight >= 0){if (s[sRight] != t[tRight])return false;}else if (sRight >= 0 || tRight >= 0)return false;sRight--;tRight--;}return true;}}