3. 双指针遍历/滑动窗口

滑动窗口框架：

l,r，valid = 0,0,0
while r < len(s):
    # c 是将移入窗口的字符
    c = s[r]
    # 右移窗口
    r += 1
    ...
    # 判断左侧窗口是否要收缩
    while window needs shrink:
        # d是要移出窗口的字符
        d = s[l]
        # 左移窗口
        l += 1
        ...

Q3. 无重复字符的最长子串 MEDIUM

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 通过次数506,928 | 提交次数1,464,272

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n<=1:
            return n
        res = 1
        l,r = 0,1
        while r<n:
            if s[r] not in s[l:r]:
                r+=1
                res = max(res,r-l)
            else:
                l+=1
        return res

Q11. 盛水最多的容器 MEDIUM

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 说明：你不能倾斜容器，且 n 的值至少为 2。 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 示例： 输入：[1,8,6,2,5,4,8,3,7] 输出：49 通过次数215,677 | 提交次数340,446

• [ ] 二分法

        #二分法
        #一开始就已经把指针定义在两端，如果短指针不动，
        #而把长指针向着另一端移动，两者的距离已经变小了，
        #无论会不会遇到更高的指针，结果都只是以短的指针来进行计算。故移动长指针是无意义的
        if len(height) == 2:
            return min(height)
        maxarea = 0
        left = 0
        right = len(height)-1
        while left < right:
            maxarea = max(min(height[left], height[right])*(right-left), maxarea)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return maxarea

• [ ] 滑动窗口法

        n = len(height)
        if n == 2:
            return min(height)
        max = 0
        windows = n-1
        while (windows > 0 ):
            for i in range(n - windows):
                minh = min(height[i],height[windows + i])
                s = minh * windows
                if max <= s:
                    max = s
            windows -= 1
        return max

  Q15. 三数之和 MEDIUM

  给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例： 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] 通过次数228,092 | 提交次数839,949

 #先排序
        if len(nums) < 3:
            return []
        nums.sort()
        result = []
        for i in range(len(nums)):
            if nums[i] > 0:
                return result
            if i > 0 and nums[i] == nums[i - 1]:
                #排除重复
                continue
            l = i+1
            r = len(nums)-1
            while l < r:
                if nums[l] + nums[r] + nums[i] == 0:
                    result.append([nums[i], nums[l], nums[r]])
                    #排除重复
                    while l < r and nums[l] == nums[l + 1]:
                        l += 1
                    while l < r and nums[r] == nums[r - 1]:
                        r -= 1
                    l += 1
                    r -= 1
                elif nums[l] + nums[r] + nums[i] < 0:
                    l += 1
                else:
                    r -= 1
        return result

Q16. 最接近的三数之和 MEDIUM

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 示例： 给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为2. (-1 + 2 + 1 = 2). 通过次数104,160 | 提交次数236,137

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        if len(nums) < 3:
            return None
        nums.sort()
        temp = nums[0] + nums[1] + nums[len(nums)-1]
        dif = abs(target - temp)
        if len(nums) == 3:
            return temp
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l = i + 1
            r = len(nums) - 1
            while (l < r):
                sum = nums[i] + nums[l] + nums[r]
                if target==sum:
                    return target
                if abs(target - sum) < dif:
                    temp = sum
                    dif = abs(target - sum)
                if abs(target - sum) >= dif:     
                    if target < sum:
                        r -= 1
                    if target >sum:
                        l += 1
        return temp

Q26. 删除排序数组中的重复项 EASY

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。 通过次数326,677 | 提交次数651,394

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n <=1:
            return n
        i,j = 0,1
        while j<n:
            if nums[j] == nums[i]:
                j+=1
            else:
                nums[i+1] = nums[j]
                j+=1
                i+=1
        return i+1

• Q42. 接雨水 HARD
• Q76. 最小覆盖子串 HARD

  给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 示例： 输入: S = “ADOBECODEBANC”, T = “ABC” 输出: “BANC” 说明： 如果 S 中不存这样的子串，则返回空字符串 “”。 如果 S 中存在这样的子串，我们保证它是唯一的答案。 通过次数54,573 | 提交次数144,413

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        '''
            need : t中每个元素出现次数
            #   t中元素也可以是重复的
            [left,right) ：窗口
            strat : 子串起点
            valid : 当前遍历的有效元素个数
            遍历时need中元素出现一次，need中元素个数减一，valid加一。当need中某个元素次数为0时，
            说明此时遍历已满足该元素的最小出现次数，再遇到该元素时，valid不变化
        '''
        from collections import defaultdict
        lens,lent = len(s),len(t)
        need = defaultdict(int)
        for i in t:
            need[i] += 1
        start, res = 0, lens + 1
        left, right = 0, 0
        valid = 0
        while right < lens:
            if s[right] in need:
                need[s[right]] -= 1
                if need[s[right]] >= 0:
                    valid += 1      
            right += 1
            while valid == lent:
                if right - left < res:
                    start = left
                    res = right - left
                if s[left] in need:
                    if need[s[left]] == 0:
                        valid -=1
                    need[s[left]] += 1
                left += 1
        return s[start:start+res] if res<lens+1 else ''

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict
        lens,lent = len(s),len(t)
        need = defaultdict(int)
        windows = {}
        for i in t:
            need[i] += 1
            windows[i] =0

        start, res = 0, lens + 1
        left, right = 0, 0
        valid = 0
        while right < lens:
            if s[right] in need:
                windows[s[right]] += 1
                if need[s[right]] == windows[s[right]]:
                    valid += 1

            right += 1
            while valid == len(need):
                if right - left < res:
                    start = left
                    res = right - left
                if s[left] in need:
                    if need[s[left]] == windows[s[left]]:
                        valid -=1
                    windows[s[left]] -= 1
                left += 1
        return s[start:start+res] if res<lens+1 else ''

76. 最小覆盖子串 HARD给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”

输出: “BANC”

说明：

如果 S 中不存这样的子串，则返回空字符串 “”。

如果 S 中存在这样的子串，我们保证它是唯一的答案。

Q209. 长度最小的子数组 MEDIUM

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。 示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 通过次数44,621 | 提交次数104,930

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        int res =n+1;
        int total =0;
        int l =0;
        int r= 0;
        while(r<n)
        {
            total += nums[r];
            while (total >=s)
            {
                res = min(res,r-l+1);
                total -=nums[l++];

            }
            r++;
        }
        return res<n+1?res:0;
    }
};

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        n = len(nums)
        res,total = n+1,0
        l,r = 0,0
        while r<n:
            total +=nums[r]
            while total>=s:
                res= min(res,r-l+1)
                total -= nums[l]
                l+=1
            r+=1
        return res if res<n+1 else 0

392. 判断子序列 EASY

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。 示例 1: s = “abc”, t = “ahbgdc” 返回 true. 示例 2: s = “axc”, t = “ahbgdc” 返回 false

all()判断迭代器 40ms 83.32% 13.5mb 100.00%

def isSubseq(s,t):
    t = iter(t)
    return all(i in t for i in s)
# 必须先对t进行iter()，因为题目要求是顺序相对位置不可变
# iter()是按迭代顺序遍历
# s = 'acb' t = 'ahbgdc' return False
[i in t for i in s]
>>>[True, True, True]
t = iter(t)
[i in t for i in s]

index = str.find(sub, start) 36ms 94.3% 13.7mb 100.00%

def ...:
    index=1
    for i in s:
        # str.find()没找到返回-1
        idnex = t.find(i, index+1)
        if index == -1:
            return False
   return True

双指针 60ms 26.53% 13.4mb 100.00%

def ...:
    ls,lt= 0,0
    while ls<len(s) and lt < len(t):
        if s[ls] == t[lt]:
            ls+=1
        lt+=1
    return ls == len(s)

Q567. 字符串的排列 MEDIUM

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = “ab” s2 = “eidbaooo” 输出: True 解释: s2 包含 s1 的排列之一 (“ba”). 示例2: 输入: s1= “ab” s2 = “eidboaoo” 输出: False 注意： 输入的字符串只包含小写字母 两个字符串的长度都在 [1, 10,000] 之间 通过次数28,344 | 提交次数78,925

‘’‘
    s1 可能包含重复字符
’‘’
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        from collections import defaultdict
        len1,len2 = len(s1),len(s2)
        if len2< len1:
            return False
        need = defaultdict(int)
        windows = {}
        for i in s1:
            need[i]+=1
            windows[i] = 0
        left,right = 0,0
        valid = 0
        while right < len2:
            if s2[right] in need:
                windows[s2[right]] +=1
                if need[s2[right]] == windows[s2[right]]:
                    valid +=1
            right+=1
            while right -left >=len1:
                if valid == len(need):
                    return True
                if s2[left] in need:
                    if windows[s2[left]] == need[s2[left]]:
                        valid-=1
                    windows[s2[left]] -=1
                left +=1


        return False

Q438. 找到字符串中所有字母异位词 MEDIUM

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。 说明： 字母异位词指字母相同，但排列不同 (包括相同）的字符串。 不考虑答案输出的顺序。 示例 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” 的字母异位词。 通过次数27,368 | 提交次数62,003

239. 滑动窗口最大值 HARD

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位 返回滑动窗口中的最大值。 进阶： 你能在线性时间复杂度内解决此题吗？ 示例:> 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3

输出: [3,3,5,5,6,7]

解释:

滑动窗口的位置 最大值

---

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        if(k==0) return res;
        if (k==1) return nums;
        // store window index from maxnum's index to minnum's index
        deque<int> index_window; 
        int r = 0;
        while(r<nums.size())
        {
            if (!index_window.empty() && index_window.front()<=r-k)
            {
                // maxnum's index not in window, pop it
                index_window.pop_front();
            }
            while (!index_window.empty() && nums[r]>nums[index_window.back()])
            {
                // next elem (nums[r]) bigger than the minnum in the current windows, pop the min
                index_window.pop_back();
            }
            index_window.push_back(r++);
            if (r>=k) res.emplace_back(nums[index_window.front()]);
        }
        return res;
    }
};