日拱两卒（十）

10#

和为K的子数组。

枚举左端点，维护潜在目标右端点的数量。

1
class Solution:
2
    def subarraySum(self, nums: List[int], k: int) -> int:
3
        n = len(nums)
4
        s = [0 for _ in range(n + 1)]
5
        cnt = defaultdict(int)
6
        for i in range(n):
7
            s[i + 1] = s[i] + nums[i]
8
            cnt[s[i + 1]] += 1
9

10
        ans = 0
11
        for l in range(1, n + 1):
12
            ans += cnt[s[l - 1] + k]
13
            cnt[s[l]] -= 1
14

15
        return ans

9#

找到字符串中所有字母异位词。

字母的种类和个数一样，顺序不要求一样就是异位词。维护定长滑动窗口里的字母种类和个数。

1
class Solution:
2
    def findAnagrams(self, s: str, p: str) -> List[int]:
3
        n, m = len(s), len(p)
4

5
        target = defaultdict(int)
6
        for i in range(m):
7
            target[p[i]] += 1
8

9
        cnt = defaultdict(int)
10
        l = 0
11
        ans = []
12

13
        def check() -> bool:
14
            for c in cnt:
15
                if target[c] != cnt[c]:
16
                    return False
17
            return True
18

19
        for r in range(n):
20
            cnt[s[r]] += 1
21
            if r - l + 1 > m:
22
                cnt[s[l]] -= 1
23
                l += 1
24
            if r - l + 1 == m and check():
25
                ans.append(l)
26

27
        return ans

8#

无重复字符的最长子串。

还是滑动窗口。

1
class Solution:
2
    def lengthOfLongestSubstring(self, s: str) -> int:
3
        n = len(s)
4
        cnt = defaultdict(int)
5

6
        ans = 0
7
        l = 0
8
        for r in range(n):
9
            cnt[s[r]] += 1
10

11
            for c in cnt:
12
                while cnt[c] > 1:
13
                    cnt[s[l]] -= 1
14
                    l += 1
15

16
            ans = max(ans, r - l + 1)
17

18
        return ans

7#

接雨水。

每一个位置的贡献是min(左侧最高木板，右侧最高木板) - 该位置模板高度。维护前后缀最大值很容易算。

题解的优化是把空间降到O(1)，相向双指针，原理是木板短的那一侧都能确定贡献，所以能移动这一侧的指针。不预计算数组而是动态维护两个变量。

没啥必要。

1
class Solution:
2
    def trap(self, height: List[int]) -> int:
3
        n = len(height)
4
        pre_max = [-1 for _ in range(n)]
5
        suf_max = [-1 for _ in range(n)]
6

7
        pre_max[0] = height[0]
8
        for i in range(1, n):
9
            pre_max[i] = max(pre_max[i - 1], height[i])
10

11
        suf_max[n - 1] = height[n - 1]
12
        for i in range(n - 2, 0, -1):
13
            suf_max[i] = max(suf_max[i + 1], height[i])
14

15
        ans = 0
16
        for i in range(1, n - 1):
17
            ans += max(0, min(pre_max[i - 1], suf_max[i + 1]) - height[i])
18
        return ans

6#

三数之和。

固定一位，剩下两位靠排序带来的单调性做双指针。

如果不用set()去重的话要跳过重复元素。

1
class Solution:
2
    def threeSum(self, nums: list[int]) -> list[list[int]]:
3
        ans = []
4
        n = len(nums)
5
        nums.sort()
6

7
        for i in range(n):
8
            if i > 0 and nums[i] == nums[i - 1]:
9
                continue
10

11
            l, r = i + 1, n - 1
12

13
            while l < r:
14
                s = nums[i] + nums[l] + nums[r]
15

16
                if s == 0:
17
                    ans.append([nums[i], nums[l], nums[r]])
18

19
                    while l < r and nums[l + 1] == nums[l]:
20
                        l += 1
21

22
                    while l < r and nums[r - 1] == nums[r]:
23
                        r -= 1
24

25
                    l += 1
26
                    r -= 1
27

28
                elif s > 0:
29
                    r -= 1
30

31
                else:
32
                    l += 1
33

34
        return ans

5#

盛最多水的容器。

相向双指针，动长的那根木板一定没收益，所以每次动短的那根木板。

1
class Solution:
2
    def maxArea(self, height: List[int]) -> int:
3
        n = len(height)
4
        l, r = 0, n - 1
5
        ans = (n - 1) * min(height[0], height[n - 1])
6

7
        while l < r:
8
            if height[l] < height[r]:
9
                l += 1
10
            else:
11
                r -= 1
12
            ans = max(ans, (r - l) * min(height[l], height[r]))
13

14
        return ans

4#

移动零。

维护不变量，把非零元素都换到前面来。

写成把零元素都换到后面去的逻辑会导致非零元素的原本顺序被打乱。

1
class Solution:
2
    def moveZeroes(self, nums: List[int]) -> None:
3
        end = 0
4
        n = len(nums)
5

6
        for i in range(n):
7
            if nums[i] != 0:
8
                nums[end], nums[i] = nums[i], nums[end]
9
                end += 1
10

11
        return

3#

最长连续序列。

101 5 1 2 3 9 4的最长连续序列指1 2 3 4 5。

维护个数，记忆化，每个元素最多被遍历一次。

1
class Solution:
2
    def longestConsecutive(self, nums: List[int]) -> int:
3
        n = len(nums)
4
        cnt = defaultdict(int)
5

6
        for i in range(n):
7
            cnt[nums[i]] += 1
8

9
        @cache
10
        def dfs(u) -> int:
11
            if not cnt.get(u - 1):
12
                return 1
13
            return 1 + dfs(u - 1)
14

15
        ans = 0
16
        for c in cnt:
17
            ans = max(ans, dfs(c))
18

19
        return ans

2#

字母异位词分组。

把字符串按照字符种类和个数分类。

1
class Solution:
2
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
3
        ans = []
4
        tot = 0
5
        mp = {}
6

7
        for s in strs:
8
            key = ''.join(sorted(s))
9
            if key not in mp:
10
                ans.append([s])
11
                mp[key] = tot
12
                tot += 1
13
            else:
14
                ans[mp[key]].append(s)
15

16
        return ans

1#

两数之和。

注意要求了一个数不能用两次。

终于！结束了！

1
class Solution:
2
    def twoSum(self, nums: List[int], target: int) -> List[int]:
3
        n = len(nums)
4
        mp = {}
5

6
        for i in range(n):
7
            if target - nums[i] in mp:
8
                return [i, mp[target - nums[i]]]
9
            mp[nums[i]] = i