hot100——双指针法专题

3.无重复字符的最长子串解题思路本题主要还是用到了滑动窗口双指针的方法python代码思路首先构造哈希表在python中哈希表一般用set或者dict来表示哈希表Python 的set和dict都是基于哈希表实现的。当只需要记录元素是否存在时用set。当需要记录元素的位置或其他附加信息时用dict如char - index。在“无重复字符的最长子串”中最简单的做法是用set存储当前窗口内的字符。当遇到重复字符时从set中移除左指针指向的字符直到重复字符被移出。C代码思路在C中一般是使用unordered_set或者是unordered_map作为哈希表来进行映射的。哈希表C 标准库提供std::unordered_set无序集合和std::unordered_map无序映射底层也是哈希表。具体思路和上述基本一致但是还是存在细微差别首先遍历字符串s并且在哈希表中对当前字符的出现次数进行计数如果当前字符的出现次数大于1的话证明当前字符在前面已经出现过因此需要从 unordered_map 中移除左指针指向的字符直到重复字符被移出。代码pythonclass Solution(object): def lengthOfLongestSubstring(self, s): :type s: str :rtype: int c set() left, maxlen 0, 0 for right in range(len(s)): while s[right] in c: c.remove(s[left]) left 1 c.add(s[right]) maxlen max(maxlen, right - left 1) return maxlenCclass Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapchar, int cnt; int left 0; int n s.size(); int maxlen 0; for(int right 0;right n;right) { char c s[right]; cnt[c]; // 说明当前窗口中存在重复元素 while(cnt[c] 1) { cnt[s[left]]--;// 移除窗口左边的字符 left;// 窗口缩小 } maxlen max(maxlen, right - left 1); } return maxlen; } };5.最长回文子串解题思路我们用中心扩展法因为如果是回文字符串的话那么从中心往两边走的话逐步比较左右元素是否相同这样就可以找到最长回文子串。而关于中心的话对于一个长度为n的字符串回文的中心可以分为以下2类字符中心每个字符本身可以作为一个奇数长度回文的中心例如aba的中心是b。一共有n个这样的中心。间隙中心每两个相邻字符之间的位置可以作为一个偶数长度回文的中心例如abba的中心在b和b之间。一共有n-1个这样的中心。所以总的中心数是nn-12n-1。那么如何一个循环遍历所有中心呢我们用一个整数i从0到2n-2共2n-1个值来代表所有中心。关键是将i映射到左右指针(l, r)使得当i为奇数的时候中心落在2个字符的间隙(偶数回文串当i为偶数时中心落在1个字符上(奇数回文串l i // 2 r (i 1) // 2当i 2k偶数时l kr k此时中心在s[k]上当i 2K 1奇数时l kr k 1此时中心落在s[k]s[k1]之间。这样一个i就对应了一个中心。代码python注意python字符串区间是左闭右开class Solution(object): def longestPalindrome(self, s): :type s: str :rtype: str n len(s) ans_left, ans_right 0, 0 for i in range(2*n - 1): l, r i//2, (i1)//2 while l0 and rn and s[l] s[r]: l - 1 r 1 if r - l -1 ans_right - ans_left: ans_left, ans_right l1, r # 左闭右开 return s[ans_left:ans_right]C(取子串用的是substr[起始位置长度])class Solution { public: string longestPalindrome(string s) { // 由中间向两边回溯 int n s.size(); int ans_left 0; int ans_right 0; for(int i 0; i 2*n -1; i) { int l i / 2; int r (i1)/2; while(l0rns[l]s[r]) { l--; r; } if(r - l - 1 ans_right - ans_left) { ans_left l1; ans_right r - 1; } } return s.substr(ans_left, ans_right - ans_left 1); } };11.盛最多水的容器解题思路首先盛最多水的容器容器的盛水量从题目中得到的是应该是两边的最小值*对应的下标差比如min(height[i], height[j]) * (j - i)取i和j分别为height数组的2端然后同时向内运动直接i和j相遇。而在此过程中究竟是移动长的还是短的那部分呢移动长的min(height[i], height[j])可能不变或者更小但是盛水量一定变小而移动短的那部分min(height[i], height[j])可能不变或者更大盛水量可能变大。算法流程初始化设定i j分别为是水槽的两端循环收窄直到i, j相遇时跳出循环更新面积值选两端中较短的那部分往中间收窄一格返回值返回面积最大值res代码pythonclass Solution(object): def maxArea(self, height): :type height: List[int] :rtype: int i, j 0, len(height) - 1 res 0 while i j: if height[i] height[j]: res max(res, height[i] * (j - i)) i 1 else: res max(res, height[j] * (j - i)) j - 1 return resCclass Solution { public: int maxArea(vectorint height) { int i 0; int j height.size() - 1; int res 0; while(i j) { if(height[i] height[j]) { res max(res, height[i]*(j - i)); i; } else { res max(res, height[j]*(j - i)); j--; } } return res; } };15.三数之和解题思路题中要求在数组中是否存在三元数能够使得nums[i] nums[j] nums[k] 0且i ! j! k根据题意我们先给整个数组排序按从小到大的顺序排序取三个数k ,i , j初始化取k遍历整个数组而i , j分别在数组的两端。循环判定结束条件ij若nums[k] nums[k-1]跳过相等的数因为整个组合都是相同的重复了取i k1 j nums.size() -1判断s nums[k] nums[i] nums[j] 0若大于0则需要j往中间靠同时一样要判定nums[j]nums[j1]以防重复若小于0则需要i往中间靠同时一样要判定nums[i] nums[i-1]以防重复若等于0则将当前的结果存入结果中ij同时往中间靠但也要同时判断nums[j]nums[j1]、nums[i] nums[i-1]以防重复。返回值返回存入的列表代码Cclass Solution { public: vectorvectorint threeSum(vectorint nums) { // 排序 sort(nums.begin(), nums.end()); vectorvectorint res; if(nums.size() 3) return res; for(int k 0;knums.size()-2;k) { if(nums[k]0) break; // j i k if(k0 nums[k] nums[k-1])//跳过nums[k]nums[k-1]的值跳过相等的值 continue; int i k 1; int j nums.size() - 1; while(i j) { int s nums[k] nums[i] nums[j]; if(s 0) { i; while(i j nums[i] nums[i-1]) { i; } } else if(s 0) { j--; while(i j nums[j] nums[j1]) { j--; } } else { res.push_back({nums[k],nums[i],nums[j]}); i; j--; while(i j nums[i] nums[i-1]) i; while(i j nums[j] nums[j1]) j--; } } } return res; } };pythonclass Solution(object): def threeSum(self, nums): :type nums: List[int] :rtype: List[List[int]] nums.sort() res, k [], 0 for k in range(len(nums) -2): if len(nums)3: break if nums[k] 0: break # 判断是否重复 if k 0 and nums[k] nums[k-1]: continue i, j k 1, len(nums) - 1 while i j: s nums[k] nums[i] nums[j] if s 0: i 1 while i j and nums[i] nums[i-1]: i 1 elif s 0: j - 1 while i j and nums[j] nums[j1]: j - 1 else: res.append([nums[k], nums[i], nums[j]]) i 1 j - 1 while i j and nums[i] nums[i-1]: i 1 while i j and nums[j] nums[j1]: j - 1 return res75.颜色分类解题思路——边界覆盖题目的要求最后要实现的效果是[0,0,0,0,0,……,1,1,1,1,1,……2,2,2,2,2]也就是三个连续区域红色、白色、蓝色。初始化开始的时候我们需要维护以下2个变量p1下一个1应该放置的位置白色区域的边界p0下一个0应该放置的位置红色区域的边界i当前位置开始p1p0i 0红色、白色区域都是空。遍历整个数组取当前元素的值保存并把当前位置的值设置为蓝色。将当前值与1和0作比较若1说明它不应该在这个位置应该放到前面的红色/白色区域那么则在p1的位置置1p1若当前值0说明当前值应该放到前面的红色区域去则在p0的位置置0p0。疑问——为什么当前值为0时还是要先经过nums[p1] 1??首先p0, p1代表红色白色边界当当前值为0时因为p0代表红色区域的边界那么当前值放到红色区域就会和白色区域的第一个元素重叠导致白色区域第一个数值被覆盖使得整体报错因此我们需要让p1先往右边移一位这样当把0放到p0边界的时候1的数值区域已经是右移了一位原本的1值不会被覆盖能够避免上述情况的发生。代码pythonclass Solution(object): def sortColors(self, nums): :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. p0, p1 0, 0 for i,x in enumerate(nums): nums[i] 2 if x1: nums[p1] 1 p1 1 if x0: nums[p0] 0 p0 1Cclass Solution { public: void sortColors(vectorint nums) { int p0 0; int p1 0; for(int i 0;inums.size();i) { int x nums[i]; nums[i] 2; if(x 1) nums[p1] 1; if(x0) nums[p0] 0; } } };解题思路——三指针取左右指针left, right分别指向数组的开头以及结尾对于数组中为0的数值和left指针指向值进行交换对于数组中为2的数值和right指针指向的值进行交换。三指针法的分区定义[0, left)已经排好的 0[left, i)已经排好的 1[i, right]待处理的元素(right, n-1]已经排好的 2初始left 0i 0right n-1。为什么与 left 交换后可以 i而与 right 交换后 i 不动关键在于交换来的元素是否“已知”。与 left 交换left指向的元素来自已处理过的 1 区域或自身。根据分区定义[left, i)区间内的元素都是 1或者为空。所以nums[left]的值只能是 1如果left i或者就是nums[i]本身如果left i此时值为 0。交换后nums[i]变成 1或保持 0这个值是已经“就绪”的不需要再次检查因此可以放心地i去处理下一个位置。与 right 交换right指向的元素来自尚未处理的区域[i, right]。这个区域的值可能是 0、1 或 2完全未知。交换后nums[i]变成了一个未检查过的新值必须留在当前位置重新判断所以不能i只能right--缩小右边的 2 区域。在三指针法荷兰国旗问题中left和i的初始值都为 0。随着算法进行left始终指向第一个不是 0 的位置即 1 区域的起点而i指向当前正在检查的元素。它们的关系是left ≤ i。当left i时表示 1 区域为空当前检查的位置正好是 0 区域的边界。代码pythonclass Solution(object): def sortColors(self, nums): :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. p0, p1 0, 0 for i,x in enumerate(nums): nums[i] 2 if x1: nums[p1] 1 p1 1 if x0: nums[p0] 0 p0 1 n len(nums) left, right 0, n -1 i 0 while i right: if nums[i] 0: nums[i], nums[left] nums[left], nums[i] left 1 i 1 elif nums[i] 2: nums[i], nums[right] nums[right], nums[i] right - 1 else: i 1Cclass Solution { public: void sortColors(vectorint nums) { /* int p0 0; int p1 0; for(int i 0;inums.size();i) { int x nums[i]; nums[i] 2; if(x 1) nums[p1] 1; if(x0) nums[p0] 0; } */ int left 0; int right nums.size() - 1; int i 0; while(i right) { if(nums[i]0) { swap(nums[i],nums[left]); left; i; } else if(nums[i] 2) { swap(nums[i], nums[right]); right--; } else{ i; } } } };76.最小覆盖子串解题思路——滑动窗口由题意可知我们需要的是在母串S中找到包含子串t中每一个字符的最小子串如果没有则返回“”。这道题明显应该使用滑动窗口来解决具体思路如下首先统计子串t中每个字符的出现次数用unordered_map need来表示,以及用valid来记录t中每种字符的种类用start以及len来表示最小子串的起点以及长度遍历s如果当前字符是需要的字符则更新当前窗口中该字符的值并判断当前字符的出现次数和need中是否一致若一致则valid。当valid的值等于t中的字符种类的时候这个时候我们已经找到了满足条件的子串但并非是最优解因此需要我们不断更新迭代判断。若valid值等于t中字符的个数则 更新最小子串起始点最小长度。然后不断缩小这个满足条件的次优解子串判断每一次缩小窗口时弹出的元素的值是否是子串计数need中的值若是如果窗口中该数的值和need中相等那么由于该数的滑出valid必须要--因此此时的窗口不满足条件了。最后返回滑动之后得到的最优解。deepseek的总结初始化left0, right0, valid0窗口为空。外层 while右指针移动取字符c s[right]右移right。如果c是需要的字符增加window[c]并检查是否恰好达到需求window[c] need[c]若是则valid。内层 while当窗口可行时尝试收缩左边界记录当前窗口长度right - left如果比minLen小则更新start和minLen。准备移出左边界字符d s[left]左移left。如果d是需要的字符且移出前window[d] need[d]即移出后就不够了则valid--然后window[d]--。继续收缩直到窗口不再可行valid need.size()。重复直到right到达末尾。返回s.substr(start, minLen)。代码C——窗口左闭右开这里需要注意一个地方就是在C中我们的代码是while(right s.size()){char c s[right];right指向的永远是下一个最后是s.size()对应的部分所以C中窗口是[left, right)是左闭右开所以对应的窗口长度是right - left。python——窗口左闭右闭python代码则是如下for right,c in enumerate(s):right永远是当前数组的元素不会出现越界情况。因此对应的窗口是[left, right]是左闭右闭。对应的窗口长度是right - left 1。pythonclass Solution(object): def minWindow(self, s, t): from collections import defaultdict :type s: str :type t: str :rtype: str left, right 0, 0 start 0 minlen float(inf) valid 0 need defaultdict(int) window defaultdict(int) # 统计t中每个字符的出现的数量 for ch in t: need[ch]1 # 滑动窗口 for right,c in enumerate(s): if c in need: window[c] 1 if window[c] need[c]: valid 1 # 注意python是左闭右开的区间 # 窗口中亦含有t中所有元素缩小左边界优化以得到最优解 # right - left 1: 当前窗口的长度 while valid len(need): if right - left 1 minlen: start left minlen right - left 1 d s[left] left 1 # 当d是t中的元素的时候再做下面的判断、处理 if d in need: if window[d]need[d]: valid - 1 window[d] - 1 return if minlenfloat(inf) else s[start:startminlen]Cclass Solution { public: string minWindow(string s, string t) { unordered_mapchar, int need, window; int valid 0; //字符串t中的字符种类数目 int start 0; int minLen INT_MAX; int left 0; int right 0; for(char c : t) need[c]; //寻找满足条件的最小覆盖字串 while(right s.size()) { char c s[right]; //若当前字符是need中需要的则进行下一步 //当前字符的数目和need中次数一致则有效种类数目1 if(need.count(c)) { window[c]; if(window[c] need[c]) valid; } // 更新得到最优解 while(validneed.size()) { if(right - left minLen) { start left; minLen right - start; } char d s[left]; left; //移出前满足移除后便不满足因此valid需要-1 if(need.count(d)) { if(window[d] need[d]) valid--; window[d]--; } } } return minLenINT_MAX? : s.substr(start, minLen); } };283.移动零解题思路题目中要求必须在不复制数组的情况下原地对数组进行操作那就是要求空间复杂度时O(1)此处我们使用一次遍历这里参考了快速排序的思路快速排序是选取一个中间点x把小于等于x的结果放到x的左边把大于x的结果放到x的右边。那么这道题我们选取0作为这个中间点不等于0的数放到数组的左边那么余下的数放到0的右边。我们取i, j这两个指针遍历nums中不是0的数将nums[i]的值和nums[j]的值做交换。代码pythonclass Solution(object): def moveZeroes(self, nums): :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. if nums is None: return j 0 for i in range(len(nums)): if nums[i] ! 0: t nums[i] nums[i] nums[j] nums[j] t j 1Cclass Solution { public: void moveZeroes(vectorint nums) { if(nums.empty()) return; // 两个指针i, j int j 0; for(int i 0; i nums.size();i){ // 把nums[i]中不等于0的值放到前面之后的就都是0 if(nums[i] ! 0) { int t nums[i]; nums[i] nums[j]; nums[j] t; } } } };参考动画演示 283.移动零287.寻找重复数解题思路本题其实还是使用双指针法但是在这个地方需要理清以下情况对于任意的数组按照当前下标---当前下标所指向的值这样可以构成序列。题目中nums含有n1个数下标从0~n数值是[1, n]其中只有一个整数出现2次或者更多其余正数均只出现一次。如果nums中出现了不同下标对应的值相同的情况那么这个nums所对应的序列中就会出现环。重复的数就是这个环的入口。举例说明一下nums [1, 3, 4, 2 , 2]下标 值0 11 32 43 24 2形成的序列就是0 - 1 - 3 - 2 - 4| |4 - 2最后一个徘徊在2-4-2-4-2……这个环当中其中环的入口就是2也就是nums中的重复的数。那么如何得到这个重复的数呢首先我们取快慢指针fast, slow初始化快慢指针都初始化为0然后快指针每一次往前走2步而慢指针每一次往前走1步。如果有重复元素的话那么快慢指针最终一定会在环内某个部分相遇假设快慢指针最终在据环的入口处c相遇假设环外的元素长度是a环的长度是b那么快指针走过的距离am*b c慢指针走过的距离an*b c其中n一定小于m。由上述2个式子可以得到am*b c 2(an*b c) ac (m-n)*b ac是环的整数倍长度那如何得到这个重复元素呢我们让一个元素从起点开始走pre1让另一个元素从slow和fast指针相遇的地方开始走pre2。当pre1走过的距离是a到达环的入口处时那么pre2走过的距离是ca, 而ca正好是换的长度的整数倍也就是说此时pre2也正好走到了环的入口处所以这俩一定会在环的入口处相遇最终pre1指向的值就是nums中的重复元素。代码pythonclass Solution(object): def findDuplicate(self, nums): :type nums: List[int] :rtype: int # 快慢指针都从起点开始出发快指针一次走2步慢指针一次走1步 fast, slow 0, 0 fast nums[nums[fast]] slow nums[slow] while fast ! slow: fast nums[nums[fast]] slow nums[slow] # 这时快慢指针相等也即找了重复元素 pre1, pre2 0, slow while pre1 ! pre2: pre1 nums[pre1] pre2 nums[pre2] # 找到了重复元素pre1 nums[pre1] return pre1Cclass Solution { public: int findDuplicate(vectorint nums) { int slow 0; int fast 0; slow nums[slow]; fast nums[nums[fast]]; while(slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } int pre1 0; int pre2 slow; while(pre1 ! pre2) { pre1 nums[pre1]; pre2 nums[pre2]; } return pre1; } };参考287.寻找重复数647.回文子串解题思路本题思路和最长回文子串的思路一致我们使用的是中心扩展法其中这里的中心有2*n-1个为什么有这么多中心可以看我上面的最长回文子串的讲解里面有在这个地方我们只需要在每一个判断是回文串的时候计数就行。代码pythonclass Solution(object): def countSubstrings(self, s): :type s: str :rtype: int n len(s) count 0 # 中心扩展法 for i in range(2*n-1): left i // 2 right (i1)//2 while left 0 and right n and s[left]s[right]: count 1 left - 1 right 1 return countCclass Solution { public: int countSubstrings(string s) { int left 0; int right 0; int count 0; // 中心扩展法 for(int i 0;i (2*(s.size()) - 1);i) { left i / 2; right (i 1) / 2; while(left0 rights.size()s[right]s[left]) { left--; right; count; } } return count; } };