双指针总结.md

双指针总结

• 基本操作：一个指针代表当前位置，一个指针代表写入位置
  • 26 删除有序数组中的重复项
  • 27 移除元素
  • 80 删除有序数组中的重复项 II
  • 283 移动零
• 首尾双指针
  • 11 盛最多水的容器
  • 15 三数之和
  • 16 最接近的三数之和
  • 18 四数之和
  • 125 验证回文串
  • 167 两数之和 II - 输入有序数组
  • 344 反转字符串
  • 345 反转字符串中的元音字母
  • 633 平方数之和
  • 680 验证回文字符串 Ⅱ
• 左右边界双指针 / 滑动窗口
  • 3 无重复字符的最长子串
  • 5 最长回文子串
  • 209 长度最小的子数组
  • 438 找到字符中的所有字母异位词
  • 567 字符串的排列
  • 594 最长和谐子序列
  • 647 回文子串：以中心点来统计数量
  • 713 乘积小于k的子数组
  • 763 划分字母区间
  • 904 水果成篮
  • 1004 最大连续一的个数
• 双输入
  • 88 合并两个有序数组
  • 844 比较含退格的字符串
  • 977 有序数组的平方
• 技巧
  • 28 实现 strStr() ：KMP算法
  • 31 下一个排列
  • 75 颜色分类：双指针/三指针swap

1004. 最大连续1的个数 III.md

给定一个二进制数组 nums 和一个整数 k ，如果可以翻转最多k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

1 <= nums.length <= 105 nums[i] 不是 0 就是 1 0 <= k <= nums.length 

classSolution: deflongestOnes(self, nums: List[int], k: int) ->int: left,right=0,0counter=0l=len(nums) res=0whileright<l: ifnums[right]==0: counter+=1whilecounter>k: ifnums[left]==0: counter-=1left+=1res=max(res, right-left+1) right+=1returnres

Tips

滑动窗口问题，这里需要对题目进行一下转换，变成窗口内最多只能有k个0，这时左右边界间的长度就是当前位置最大1的情况

11. 盛最多水的容器.md

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1] 输出：1

示例 3：

输入：height = [4,3,2,1,4] 输出：16

示例 4：

输入：height = [1,2,1] 输出：2

提示：

n == height.length 2 <= n <= 105 0 <= height[i] <= 104 

classSolution: defmaxArea(self, height: List[int]) ->int: ifnotheight: return0area=0i=0j=len(height)-1whilei<j: ifheight[i] <height[j]: area=max(area, (height[i] * (j-i))) i+=1else: area=max(area, (height[j]* (j-i))) j-=1returnarea

Tips

1. 首尾双指针向前遍历，唯一的技巧在于，移动指针的时候先移动高度更低的指针，因为盛水的量受到短板的影响，所以优先移动短板

125. 验证回文串.md

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama" 输出: true 解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: "race a car" 输出: false 解释："raceacar" 不是回文串

提示：

1 <= s.length <= 2 * 105 字符串 s 由 ASCII 字符组成 

classSolution: defisPalindrome(self, s: str) ->bool: s=s.strip() i=0j=len(s)-1whilei<j: print(i,j) ifnots[i].isalnum(): i+=1continueifnots[j].isalnum(): j-=1continueifs[i].lower()!=s[j].lower(): returnFalseelse: i+=1j-=1returnTrue

Tips

就一个新知识就是isalnum()， 判断字符是否非空，且是numeric or alpha

15. 三数之和.md

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = [] 输出：[]

示例 3：

输入：nums = [0] 输出：[]

提示：

0 <= nums.length <= 3000 -105 <= nums[i] <= 105 

classSolution: defthreeSum(self, nums: List[int]) ->List[List[int]]: iflen(nums)<3: return [] nums=sorted(nums) n=len(nums) res= [] foriinrange(n-2): if (i!=0) & (nums[i]==nums[i-1]): continuetarget=-nums[i] third=n-1second=i+1whilesecond<third: if (second!=i+1) & (nums[second]==nums[second-1]): second+=1continueifnums[second]+nums[third] ==target: res.append([nums[i],nums[second],nums[third]]) #second+=1third-=1elifnums[second]+nums[third]<target: second+=1else: third-=1returnres

TIps

双指针解法

• 指针1向前遍历，只判断是否重复，重复跳过
• 指针2/3是左右指针向中间遍历

16. 最接近的三数之和.md

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4 

通过次数262,674 提交次数572,143

classSolution: defthreeSumClosest(self, nums: List[int], target: int) ->int: nums=sorted(nums) n=len(nums) distance=2**32-1foriinrange(n-2): j=i+1k=n-1whilej<k: total=nums[i]+nums[j]+nums[k] iftotal==target: returntargetifabs(target-total )<distance: distance=abs(target-total ) result=totaliftotal<target: j+=1else: k-=1returnresult

Tips

1. 和三数之和的解法一样，只不过题目住说明只有唯一解，所以不需要判断重复值，在寻找最接近的过程中加入全局变量不断判断最接近的distance即可

167. 两数之和 II - 输入有序数组.md

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

示例 1：

输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2：

输入：numbers = [2,3,4], target = 6 输出：[1,3]

示例 3：

输入：numbers = [-1,0], target = -1 输出：[1,2]

提示：

2 <= numbers.length <= 3 * 104 -1000 <= numbers[i] <= 1000 numbers 按 非递减顺序 排列 -1000 <= target <= 1000 仅存在一个有效答案 

classSolution: deftwoSum(self, numbers: List[int], target: int) ->List[int]: i=0j=len(numbers)-1whilei<j: ifnumbers[i] +numbers[j] ==target: returni+1,j+1elifnumbers[i] +numbers[j] >target: j-=1else: i+=1

Tips

1. 类比两数之和I，数组无序时一遍遍历一遍用Hash存储历史数据，数组有序时用两指针分别从小到大，从大到小遍历

18. 四数之和.md

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：

0 <= a, b, c, d < n a、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target 

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200 -109 <= nums[i] <= 109 -109 <= target <= 109 

classSolution: deffourSum(self, nums: List[int], target: int) ->List[List[int]]: nums=sorted(nums) n=len(nums) res= [] ifn<4: returnresforiinrange(n-3): if (i!=0) and (nums[i]==nums[i-1]): continueforjinrange(i+1, n-2): if (j!=i+1) and (nums[j]==nums[j-1]): continuex=j+1y=n-1whilex<y: if (x!=j+1) and (nums[x]==nums[x-1]): x+=1continueif (y!=n-1) and (nums[y]==nums[y+1]): y-=1continuetotal=nums[i]+nums[j]+nums[x]+nums[y] iftotal==target: res.append([nums[i],nums[j],nums[x],nums[y]]) x+=1y-=1eliftotal<target: x+=1else: y-=1returnres

Tips

在三数之和外面家一层循环O（N^ 3）

1. 第一个i指针顺序遍历，第二个指针i+1，剩余两个指针在剩下的空间进行二分搜索
2. 核心在于剔除重复的解

209. 长度最小的子数组.md

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4] 输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0

提示：

1 <= target <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 105 

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。 

classSolution: defminSubArrayLen(self, target: int, nums: List[int]) ->int: total=0res=2**32pointer=0foriinrange(len(nums)): total+=nums[i] whiletotal>=target: res=min(res, i-pointer+1) total-=nums[pointer] pointer+=1ifres==2**32: return0returnres

Tips

1. 如果使用暴力解法复杂度是O(n^2)
2. 这里使用双指针解法，一个指针正常遍历数组，另外一个指针当当前子序列之和>=target的时候，开始向前移动直到sum<target

26. 删除有序数组中的重复项.md

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }

示例 1：

输入：nums = [1,1,2] 输出：2, nums = [1,2] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 3 * 104 -104 <= nums[i] <= 104 nums 已按升序排列 

classSolution: defremoveDuplicates(self, nums: List[int]) ->int: index=0foriinnums[1:]: ifi!=nums[index]: index+=1nums[index]=ireturnindex+1

Tips:

双指针解法一个遍历数组，一个只有当当前元素不重复的情况下再向前移动的指针

264.丑数II.md

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1 输出：1 解释：1 通常被视为丑数。

提示：

1 <= n <= 1690

classSolution: defnthUglyNumber(self, n: int) ->int: ans= [0] * (n+1) ans[1] =1idx1, idx2,idx3=1,1,1idx=2whileidx<=n: a,b,c=ans[idx1] *2, ans[idx2]*3, ans[idx3]*5m=min(a,b,c) ifm==a: idx1+=1ifm==b: idx2+=1ifm==c: idx3+=1ans[idx]=midx+=1print(ans) returnans[n]

Tips

1. 归并排序问题，这里放在双指针了，因为需要三个指针分别指向丑数2， 丑数3，丑数*5下一个最小的位置，合并是每次选择最小的并移动指针
2. 需要注意的是因为同一个丑数可能来源于不同的指针，例如6，同时是丑数2的倍数，也是丑数3的倍数，所以指针移动时是不是互斥的

27. 移除元素.md

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }

示例 1：

输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示：

0 <= nums.length <= 100 0 <= nums[i] <= 50 0 <= val <= 100 

classSolution: defremoveElement(self, nums: List[int], val: int) ->int: index=0foriinnums: ifi!=val: nums[index] =iindex+=1returnindex

Tips:

1. 和前一题删除数组中的重复项思路是一样的，加一个额外的指针

28. 实现 strStr().md

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = "hello", needle = "ll" 输出：2

示例 2：

输入：haystack = "aaaaa", needle = "bba" 输出：-1

示例 3：

输入：haystack = "", needle = "" 输出：0

提示：

0 <= haystack.length, needle.length <= 5 * 104 haystack 和 needle 仅由小写英文字符组成 

1. 朴素方法：遍历每个字符看是否==needle，复杂度O(m*n)

2. KMP算法复杂度O(m+n)

• 生成每个字符的偏移表，即该字符在needle中是否出现，以及出现的位置

classSolution: defstrStr(self, haystack: str, needle: str) ->int: defgetnext(needle): #如果当前不匹配，下一步从needle的第几个位置开始匹配l=len(needle) next= [-1] *lptr1=0#遍历指针ptr2=-1#前缀指针whileptr1< (l-1): ifptr2==-1orneedle[ptr1]==needle[ptr2]: ptr1+=1ptr2+=1next[ptr1] =ptr2else: ptr2=next[ptr2] returnnextifnotneedle: return0next=getnext(needle) i=j=0b=len(haystack) a=len(needle) while (i<bandj<a): ifj==-1orneedle[j] ==haystack[i]: i+=1j+=1else: j=next[j] ifj==a: returni-jelse: return-1

1. 生成next指针：
   1. 如果当前不匹配，下一步从needle的第几个位置开始匹配
      1. 第一个位置为-1，用来指示haystack向前移动一位，和needle首位开始匹配
      2. 其余无前缀的位置为0，意味着haystack当前位置和needle首位开始匹配
      3. 有前缀的为前缀位置i，意味着haystack当前位置和needle[i]开始匹配
2. 双指针遍历
   1. 当j=-1，都向前移动一位，haystack从下一位匹配，needle从首位匹配
   2. 当当前位置匹配，向前移动一位
   3. 当不匹配，needle指针根据next会退到对应位置

283. 移动零.md

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。 尽量减少操作次数。 

classSolution: defmoveZeroes(self, nums: List[int]) ->None: """ Do not return anything, modify nums in-place instead. """n=len(nums) index=0foriinnums: ifi!=0: nums[index]=iindex+=1nums[index:] = [0] * (n-index)

Tips

和剔除有序数组中的重复元素是相同的思路，通过额外的pointer来保留想要保留的元素

3. 无重复字符的最长子串.md

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = "" 输出: 0

提示：

0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成 

classSolution: deflengthOfLongestSubstring(self, s: str) ->int: dic= {} length=0index=-1fori,jinenumerate(s): pre_index=dic.get(j,-1) ifpre_index>index: #当存在曾经出现的字符后才更新index，重新计算index=pre_indexdic[j] =ilength=max(length, i-index) returnlength

Tips:

双指针滑动窗口解法，一个指针记录上一个最近的相同字符出现的位置，一个指针遍历当前位置

1. 只要没有出现重复字符就持续向前迭代，只有当出现重复字符后更新index重新计数
2. 从-1开始，因为如果出现重复应该是从i+1开始遍历，但是第一个字母一定不重复所以不应该从0开始应该从-1开始

31. 下一个排列.md

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须** 原地 **修改，只允许使用额外常数空间。

示例 1：

输入：nums = [1,2,3] 输出：[1,3,2] 

示例 2：

输入：nums = [3,2,1] 输出：[1,2,3] 

示例 3：

输入：nums = [1,1,5] 输出：[1,5,1] 

示例 4：

输入：nums = [1] 输出：[1] 

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ index = -1 n=len(nums) for i in range(n-2,-1,-1): if nums[i] < nums[i+1]: index = i print(index) break if index ==-1: #nums完全降序排列，转换成升序 nums[:] = nums[::-1] return nums #switch bigger value with index for i in range(n-1,index,-1): if nums[i]> nums[index]: nums[i], nums[index] = nums[index],nums[i] break nums[index+1:] = nums[index+1:][::-1] return nums 

Tips

1. 举个例子4987
2. 从后往前搜索，[j,end]必须是降序，找到第一个非降序i A[i]<A[j]【4，9】
3. 在[j,end]中搜索到min(A[k])>A[i], i和k交换顺序【4和7】
4. 把[j,end]进行reorder变成升序【7489】

344. 反转字符串.md

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]

提示：

1 <= s.length <= 105 s[i] 都是 ASCII 码表中的可打印字符 

classSolution: defreverseString(self, s: List[str]) ->None: """ Do not return anything, modify s in-place instead. """i=0j=len(s)-1whilei<j: s[i],s[j] =s[j],s[i] i+=1j-=1

345. 反转字符串中的元音字母.md

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 'a'、'e'、'i'、'o'、'u'，且可能以大小写两种形式出现。

示例 1：

输入：s = "hello" 输出："holle"

示例 2：

输入：s = "leetcode" 输出："leotcede"

提示：

1 <= s.length <= 3 * 105 s 由 可打印的 ASCII 字符组成 

classSolution: defreverseVowels(self, s: str) ->str: white_list= {'a','e','i','o','u','A','E','I','O','U'} i=0j=len(s)-1s=list(s) whilei<j: if (s[i] inwhite_list) and (s[j] inwhite_list): s[i],s[j] =s[j],s[i] i+=1j-=1elifs[i] inwhite_list: j-=1elifs[j] inwhite_list: i+=1else: i+=1j-=1return''.join(s)

Tips

没啥多说的，都是双指针的解法，类似的还有反转数组，

438. 找到字符串中所有字母异位词.md

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

1 <= s.length, p.length <= 3 * 104 s 和 p 仅包含小写字母 

classSolution: deffindAnagrams(self, s: str, p: str) ->List[int]: n, m, res=len(s), len(p), [] ifn<m: returnresp_cnt= [0] *26s_cnt= [0] *26foriinrange(m): p_cnt[ord(p[i]) -ord('a')] +=1s_cnt[ord(s[i]) -ord('a')] +=1ifs_cnt==p_cnt: res.append(0) foriinrange(m, n): s_cnt[ord(s[i-m]) -ord('a')] -=1s_cnt[ord(s[i]) -ord('a')] +=1ifs_cnt==p_cnt: res.append(i-m+1) returnres

Tips

用了滑动窗口记录在s中每个len(p)的窗口s的Counter，每次向前移动一位就进行一次更新

5. 最长回文子串.md

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd" 输出："bb"

示例 3：

输入：s = "a" 输出："a"

示例 4：

输入：s = "ac" 输出："a"

提示：

1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成 

classSolution: deflongestPalindrome(self, s: str) ->str: l=len(s) ifl<=1: returnsdefget_boundary(left, right): whileleft>=0andright<lands[left] ==s[right]: left-=1right+=1returnleft, rightstart, end=0,0foriinrange(0, l-1): left1, right1=get_boundary(i, i+1) left2, right2=get_boundary(i, i+2) ifright1-left1>end-start: start=left1end=right1ifright2-left2>end-start: start=left2end=right2returns[(start+1):end]

Tips

动态规划和双指针的解法都是O(n^2)的复杂度，那当然是双指针的解法想起来更容易一些。从中心点出发向左右扩充寻找左右边界即可

567. 字符串的排列.md

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba").

示例 2：

输入：s1= "ab" s2 = "eidboaoo" 输出：false

提示：

1 <= s1.length, s2.length <= 104 s1 和 s2 仅包含小写字母 

classSolution: defcheckInclusion(self, s1: str, s2: str) ->bool: defseralize(s): dic= [0] *26foriins: dic[ord(i)-ord('a')]+=1returndicl=len(s1) dic1=seralize(s1) dic2=seralize(s2[:len(s1)]) foriinrange(l,len(s2)): ifdic1==dic2: returnTruedic2[ord(s2[i-l])-ord('a')]-=1dic2[ord(s2[i])-ord('a')]+=1returndic1==dic2

594. 最长和谐子序列.md

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

示例 1：

输入：nums = [1,3,2,2,5,2,3,7] 输出：5 解释：最长的和谐子序列是 [3,2,2,2,3]

示例 2：

输入：nums = [1,2,3,4] 输出：2

示例 3：

输入：nums = [1,1,1,1] 输出：0

提示：

1 <= nums.length <= 2 * 104 -109 <= nums[i] <= 109 

1. 哈希解法

classSolution: deffindLHS(self, nums: List[int]) ->int: fromcollectionsimportdefaultdictdic=defaultdict(int) foriinnums: dic[i]+=1ans=0foriindic: ifi+1indic: ans=max(ans, dic[i]+dic[i+1]) returnans

空间复杂度O(n)

时间复杂度O(n)

2. 滑动窗口

classSolution: deffindLHS(self, nums: List[int]) ->int: nums.sort() maxlen=0left=0foriinrange(1, len(nums)): whileleft>=0andleft<iandnums[i]-nums[left]>1: left+=1ifnums[i]-nums[left]==1: maxlen=max(maxlen, i-left+1) returnmaxlen

空间复杂度O(1)

时间复杂度O(blogs)

633. 平方数之和.md

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

示例 1：

输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3 输出：false

提示：

0 <= c <= 231 - 1 

classSolution: defjudgeSquareSum(self, c: int) ->bool: low=0high=int(c**0.5) whilelow<=high: total=low**2+high**2iftotal==c: returnTrueeliftotal<c: low+=1else: high-=1returnFalse

Tips

双指针左右收缩边界

647. 回文子串.md

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：s = "abc" 输出：3 解释：三个回文子串: "a", "b", "c"

示例 2：

输入：s = "aaa" 输出：6 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示：

1 <= s.length <= 1000 s 由小写英文字母组成 

1. 动态规划

classSolution: defcountSubstrings(self, s: str) ->int: l=len(s) counter=0dp= [[False]*lfor_inrange(l)] foriinrange(l-1,-1,-1): forjinrange(i,l): ifs[i]==s[j]: ifj-i<=1: counter+=1dp[i][j] =Trueelse: ifdp[i+1][j-1]: counter+=1dp[i][j]=Truereturncounter

Tip

1. $dp[i][j]$是【i，j】之间字符是否是回文字符，每碰到一个true，result+=1

2. 状态转移

   1. s[i]==s[j]:
      1. j-1<=1:result+1
      2. 需要进一步判断内部是否为回文$dp[i+1][j-1]$
   2. s[i]!=s[j]: 没啥可说的继续保持False的常态

3. 初始化都是False即可，因为会从i==j的对角线开始更新所以不需要特殊的初始化

4. 遍历顺序，因为$dp[i][j]$$需要用到$$dp[i+1][j-1]$ 所以很自然是向左上方矩阵进行更新。

5. 双指针解法

classSolution: defcountSubstrings(self, s: str) ->int: l=len(s) defcount_substring(ptr1,ptr2): counter=0whileptr1>=0andptr2<lands[ptr1]==s[ptr2]: counter+=1ptr1-=1ptr2+=1returncounterres=0foriinrange(l): n1=count_substring(i,i) res+=n1ifi<l-1: n2=count_substring(i,i+1) res+=n2returnres

Tips

回文串感觉用简单明了的双指针还是更简单一些，只需要判断从每个位置开始（奇/偶）分别有几个回文串就行

680. 验证回文字符串 Ⅱ.md

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: s = "aba" 输出: true

示例 2:

输入: s = "abca" 输出: true 解释: 你可以删除c字符。

示例 3:

输入: s = "abc" 输出: false

提示:

1 <= s.length <= 105 s 由小写英文字母组成 

classSolution: defvalidPalindrome(self, s: str) ->bool: defcheckPalindrom(left, right): whileleft<right: ifs[left]==s[right]: left+=1right-=1else: returnFalsereturnTrueleft=0right=len(s)-1whileleft<right: ifs[left]==s[right]: left+=1right-=1else: check=checkPalindrom(left+1, right) orcheckPalindrom(left, right-1) returncheckreturnTrue

Tips

用相同的方式在出现不是回文字符的时候，移一位继续检查

713. 乘积小于K的子数组.md

给定一个正整数数组 nums和整数 k 。

请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入: nums = [10,5,2,6], k = 100 输出: 8 解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。 需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

示例 2:

输入: nums = [1,2,3], k = 0 输出: 0

提示:

1 <= nums.length <= 3 * 104 1 <= nums[i] <= 1000 0 <= k <= 106 

classSolution: defnumSubarrayProductLessThanK(self, nums: List[int], k: int) ->int: ifk<=1: return0left=0total=1ans=0foriinrange(len(nums)): total*=nums[i] whiletotal>=k: total//=nums[left] left+=1ans+= (i-left+1) returnans

双指针+滑动窗口，统计的子数组的技巧在于每一步只统计以最右侧元素为pivot的数组长度，[1,2,3]k=10, 则每一步分别统计以1，2，3分别结尾的数组长度为1，2，3的窗口里的数组长度

75. 颜色分类.md

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1] 输出：[0,1,2]

示例 3：

输入：nums = [0] 输出：[0]

示例 4：

输入：nums = [1] 输出：[1]

提示：

n == nums.length 1 <= n <= 300 nums[i] 为 0、1 或 2 

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？ 你能想出一个仅使用常数空间的一趟扫描算法吗？ 

classSolution: defsortColors(self, nums: List[int]) ->None: """ Do not return anything, modify nums in-place instead. """p0=p1=0foriinrange(len(nums)): ifnums[i]==1: nums[i], nums[p1] =nums[p1], nums[i] p1+=1elifnums[i]==0: nums[i],nums[p0] =nums[p0], nums[i] ifp0<p1: nums[i], nums[p1] =nums[p1], nums[i] p1+=1p0+=1

Tips

1. 如果是单指针需要遍历两次，第一次把所有的0都移到最前面，第二次吧所有的1都移到0的后面
2. 如果是双指针，一个指向0的位置，一个指向1的位置，唯一需要注意的就是因为0和1本身有位置要求，所以当双指针位置不满足的时候需要进行二次换位

763. 划分字母区间.md

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。

示例：

输入：S = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca", "defegde", "hijhklij"。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

S的长度在[1, 500]之间。 S只包含小写字母 'a' 到 'z' 。 

classSolution: defpartitionLabels(self, s: str) ->List[int]: pos= {} foriinrange(len(s)): pos[s[i]] =ileft=0right=0res= [] foriinrange(len(s)): right=max(right, pos[s[i]]) ifi==right: res.append(right-left+1) left=i+1returnres

Tips

贪心+双指针滑动区间

1. 碰到区间问题，必要先统计位置。在当前位置之需要判断是否更新右边界，以及是否达到了右边界，达到后更新区间和左边界。
2. 最开始以为需要维护左右两个边界，后来发现只要在右边界到达之前有其他字母更新更远的右边界即可

80. 删除有序数组中的重复项 II.md

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }

示例 1：

输入：nums = [1,1,1,2,2,3] 输出：5, nums = [1,1,2,2,3] 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3] 输出：7, nums = [0,0,1,1,2,3,3] 解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

提示：

1 <= nums.length <= 3 * 104 -104 <= nums[i] <= 104 nums 已按升序排列 

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

classSolution: defremoveDuplicates(self, nums: List[int]) ->int: pos=1counter=1cur=nums[0] foriinnums[1:]: ifi!=cur: nums[pos]=icur=icounter=1pos+=1elifcounter<2: nums[pos]=icounter+=1pos+=1returnpos

844. 比较含退格的字符串.md

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。

如果相等，返回 true ；否则，返回 false 。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c" 输出：true 解释：S 和 T 都会变成 “ac”。

示例 2：

输入：s = "ab##", t = "c#d#" 输出：true 解释：s 和 t 都会变成 “”。

示例 3：

输入：s = "a##c", t = "#a#c" 输出：true 解释：s 和 t 都会变成 “c”。

示例 4：

输入：s = "a#c", t = "b" 输出：false 解释：s 会变成 “c”，但 t 仍然是 “b”。

提示：

1 <= s.length, t.length <= 200 s 和 t 只含有小写字母以及字符 '#' 

进阶：

你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？ 

1. 简单的栈解法：多了O（N+M）的内存占用

classSolution: defbackspaceCompare(self, s: str, t: str) ->bool: defrebuild(s): news= [] foriinrange(len(s)): ifs[i]!='#': news.append(s[i]) else: try: news.pop() except: continuereturnnewsreturnrebuild(s)==rebuild(t)

2. 技巧从后向前遍历

# class Solution:# def backspaceCompare(self, s: str, t: str) -> bool:# def rebuild(s):# news = []# for i in range(len(s)):# if s[i]!='#':# news.append(s[i])# else:# try:# news.pop() # except:# continue # return news # return rebuild(s)==rebuild(t)classSolution: defbackspaceCompare(self, s: str, t: str) ->bool: i=len(s)-1j=len(t)-1skips=0skipt=0whilei>=0orj>=0: whilei>=0: ifs[i]=='#': skips+=1i-=1elifskips>0: i-=1skips-=1else: breakwhilej>=0: ift[j]=='#': skipt+=1j-=1elifskipt>0: j-=1skipt-=1else: breakifi<0andj<0: returnTrueelifi<0orj<0: returnFalseelifs[i]!=t[j]: returnFalseelse: i-=1j-=1returnTrue

Tips

如果用双指针法，corner case要注意的点真的是多到爆炸。。。

1. 每个数组都是各自遍历直到第一个valid的字符，遍历过程不断统计需要skip的字符（注意一次只能skip一个，如果skip多个可能会skip掉#）
2. 到valid字符时，需要再判断一次pos，当两个pos都>=0时判断数值是否一样，当两个pos有一个>=0时为False，如果两个都<=0这里是True！

88. 合并两个有序数组.md

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109 

解法1. 额外占用O（m+n）的空间

classSolution: defmerge(self, nums1: List[int], m: int, nums2: List[int], n: int) ->None: """ Do not return anything, modify nums1 in-place instead. """nums=[] i=0j=0whileTrue: ifi==m: nums+=nums2[j:n] breakifj==n: nums+=nums1[i:m] breakifnums1[i]<nums2[j]: nums.append(nums1[i]) i+=1else: nums.append(nums2[j]) j+=1print(nums) nums1[:]=nums

解法2.直接在nums1上修改，nums1连地方都给你留好了，干啥不用

classSolution: defmerge(self, nums1: List[int], m: int, nums2: List[int], n: int) ->None: """ Do not return anything, modify nums1 in-place instead. """i=m+n-1m-=1n-=1whileTrue: ifm<0: nums1[:n+1] =nums2[:n+1] breakifn<0: breakifnums1[m] >nums2[n]: nums1[i] =nums1[m] m-=1else: nums1[i] =nums2[n] n-=1i-=1

Tips

1. 以上是O(m+n)的解法，空间占用也是O(m+n)
2. 需要注意的是最后是在原地修改nums1，在原地修改不能直接赋值，需要在原始container中修改nums[:]

904. 水果成篮.md

在一排树中，第 i 棵树产生 tree[i] 型的水果。 你可以从你选择的任何树开始，然后重复执行以下步骤：

把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。 

请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。

你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。

用这个程序你能收集的水果树的最大总量是多少？

示例 1：

输入：[1,2,1] 输出：3 解释：我们可以收集 [1,2,1]。

示例 2：

输入：[0,1,2,2] 输出：3 解释：我们可以收集 [1,2,2] 如果我们从第一棵树开始，我们将只能收集到 [0, 1]。

示例 3：

输入：[1,2,3,2,2] 输出：4 解释：我们可以收集 [2,3,2,2] 如果我们从第一棵树开始，我们将只能收集到 [1, 2]。

示例 4：

输入：[3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：我们可以收集 [1,2,1,1,2] 如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 棵水果树。

提示：

1 <= tree.length <= 40000 0 <= tree[i] < tree.length 

classSolution: deftotalFruit(self, fruits: List[int]) ->int: fromcollectionsimportdefaultdictcount=defaultdict(int) num=0left=0l=len(fruits) forrightinrange(l): count[fruits[right]]+=1whilelen(count)>=3: count[fruits[left]]-=1ifcount[fruits[left]] ==0: delcount[fruits[left]] left+=1num=max(num, right-left+1) returnnum

Tips

左右双指针问题，和209长度右指针顺序遍历，左指针只有当[left,right]之间的水果>=3种的时候开始i向前移动直到剩下两种

977. 有序数组的平方.md

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 已按 非递减顺序 排序 

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题 

classSolution: defsortedSquares(self, nums: List[int]) ->List[int]: #找到负数的位置neg_pos=-1fori,jinenumerate(nums): ifj<0: neg_pos=ielse: breakresult= [] pos_pos=neg_pos+1l=len(nums) whileneg_pos>=0orpos_pos<l: ifneg_pos<0: result.append(nums[pos_pos]**2) pos_pos+=1elifpos_pos>=l: result.append(nums[neg_pos]**2) neg_pos-=1elifnums[neg_pos]**2<nums[pos_pos]**2: result.append(nums[neg_pos]**2) neg_pos-=1elifnums[neg_pos]**2>=nums[pos_pos]**2: result.append(nums[pos_pos]**2) pos_pos+=1returnresult

Tips

这里的双指针是双输入问题，一个是正数部分，一个是负数部分，进行sort merge