• 一、基础算法精讲:双指针


    1、相向双指针 1

    1.1 两数之和 II - 输入有序数组

    Leetcode 167

    注意,这里可以使用相向双指针的原因是因为这里的数组是非递减的。

    class Solution:
        def twoSum(self, numbers: List[int], target: int) -> List[int]:
            l = 0
            r = len(numbers) - 1
            while True:
                s = numbers[l] + numbers[r]
                if s == target:
                    return [l + 1, r + 1]
                if s > target:
                    r -= 1
                else:
                    l += 1
    
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    class Solution {
    public:
        vector<int> twoSum(vector<int>& numbers, int target) {
            int l = 0, r = numbers.size() - 1;
            while (true) {
                int s = numbers[l] + numbers[r];
                if (s == target) return {l + 1, r + 1};
                s > target ? r -- : l ++ ;
            }
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    1.2 三数之和

    Leetcode 15

    需要注意三个问题:

    • 如何处理 【不重复三元组】这个问题?排序,对于每一个指针跳过重复元素。
    • 优化一:在数组已经从小到大排序的前提下,如果当前元素加上后面两个元素的值已经大于零,那么当前元素加上后面任意两个元素都会大于零,不符合条件,直接 break。
    • 优化二:在数组已经从小到大排序的前提下,如果当前元素加上数组最后两个元素的值小于零,那么当前元素加上该元素后面所有元素都会小于零,直接 continue。

    这个题与 1.6 类似,思路都是优先固定一个节点然后使用双指针去寻找另外两个节点。

    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            nums.sort()
            ans = []
            n = len(nums)
            for i in range(n - 2):
                x = nums[i]
                if i > 0 and x == nums[i - 1]:  # 跳过重复数字
                    continue
                if x + nums[i + 1] + nums[i + 2] > 0:  # 优化一
                    break
                if x + nums[-2] + nums[-1] < 0:  # 优化二
                    continue
                j = i + 1
                k = n - 1
                while j < k:
                    s = x + nums[j] + nums[k]
                    if s > 0:
                        k -= 1
                    elif s < 0:
                        j += 1
                    else:
                        ans.append([x, nums[j], nums[k]])
                        j += 1
                        while j < k and nums[j] == nums[j - 1]:  # 跳过重复数字
                            j += 1
                        k -= 1
                        while k > j and nums[k] == nums[k + 1]:  # 跳过重复数字
                            k -= 1
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            vector<vector<int>> ans;
            int n = nums.size();
            for (int i = 0; i < n - 2; i ++ ) {
                int x = nums[i];
                if (i && x == nums[i - 1]) continue;  // 跳过重复数字
                if (x + nums[i + 1] + nums[i + 2] > 0) break;  // 优化一
                if (x + nums[n - 1] + nums[n - 2] < 0) continue;  // 优化二
                int j = i + 1, k = n - 1;
                while (j < k) {
                    int s = x + nums[j] + nums[k];
                    if (s > 0) k -- ;
                    else if (s < 0) j ++ ;
                    else {
                        ans.push_back({x, nums[j], nums[k]});
                        for ( ++ j; j < k && nums[j] == nums[j - 1]; j ++ );  // 跳过重复元素
                        for ( -- k; k > j && nums[k] == nums[k + 1]; k -- );  // 跳过重复元素
                    }
                }
            }
            return ans;
        }
    }; 
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    1.3 最接近的三数之和

    Leetcode 16

    注意这里的三个优化:

    class Solution:
        def threeSumClosest(self, nums: List[int], target: int) -> int:
            nums.sort()
            n = len(nums)
            minDiff = inf
            ans = 0
    
            for i in range(n - 2):
                x = nums[i]
    
                # 优化三
                if i and x == nums[i - 1]: 
                    continue
    
                # 优化一
                s = x + nums[i + 1] + nums[i + 2]
                if s > target:
                    if s - target < minDiff:
                        minDiff = s - target
                        ans = s
                    break
                
                # 优化二
                s = x + nums[-1] + nums[-2]
                if s < target:
                    if target - s < minDiff:
                        minDiff = target - s
                        ans = s
                    continue
    
                j, k = i + 1, n - 1
                while j < k:
                    s = x + nums[j] + nums[k]
    
                    if s == target:
                        return s
    
                    if s > target:      
                        if s - target < minDiff:
                            minDiff = s - target
                            ans = s      
                        k -= 1 
                    else:
                        if target - s < minDiff:
                            minDiff = target - s
                            ans = s
                        j += 1
    
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            int res;
            int min_diff = 1e9;
            int n = nums.size();
            sort(nums.begin(), nums.end());
            for (int i = 0; i < n - 2; i ++ ) {
                int x = nums[i];
    
                // 优化一
                if (i && x == nums[i - 1]) continue;
    
                // 优化二
                int s = x + nums[i + 1] + nums[i + 2];
                if (s > target) {
                    if (s - target < min_diff) 
                        min_diff = s - target, res = s;
                    break;
                }
                
                // 优化三
                s = x + nums[n - 2] + nums[n - 1];
                if (s < target) {
                    if (target - s < min_diff)
                        min_diff = target - s, res = s;
                    continue;
                }
    
                int j = i + 1, k = n - 1;
                while (j < k) {
                    s = x + nums[j] + nums[k];
                    if (s == target) return s;
                    if (s > target) {
                        if (s - target < min_diff)
                            min_diff = s - target, res = s;
                            k -- ;
                    } else {
                        if (target - s < min_diff)
                            min_diff = target - s, res = s;
                        j ++ ;
                    }
                }
            }
            return res;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    1.4 四数之和

    Leetcode 18

    class Solution:
        def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
            nums.sort()
            n = len(nums)
            ans = []
            for a in range(n - 3):
                x = nums[a]
                if a and x == nums[a - 1]: 
                    continue
                if x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target: 
                    break
                if x + nums[-1] + nums[-2] + nums[-3] < target: 
                    continue;
                for b in range(a + 1, n - 2):
                    y = nums[b]
                    if b > a + 1 and y == nums[b - 1]: 
                        continue
                    if x + y + nums[b + 1] + nums[b + 2] > target: 
                        break
                    if x + y + nums[-1] + nums[-2] < target: 
                        continue
                    
                    c, d = b + 1, n - 1
                    while c < d:
                        s = x + y + nums[c] + nums[d]
                        if s > target: 
                            d -= 1
                        elif s < target: 
                            c += 1
                        else: 
                            ans.append([x, y, nums[c], nums[d]])
                            c += 1
                            while c < d and nums[c] == nums[c - 1]: 
                                c += 1
                            d -= 1
                            while c < d and nums[d] == nums[d + 1]: 
                                d -= 1
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> ans;
            int n = nums.size();
            sort(nums.begin(), nums.end());
            for (int a = 0; a < n - 3; a ++ ) {
                long long x = nums[a];
                if (a && x == nums[a - 1]) continue;
                if (x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break;
                if (x + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) continue;
                for (int b = a + 1; b < n - 2; b ++ ) {
                    long long y = nums[b];
                    if (b > a + 1 && y == nums[b - 1]) continue;
                    if (x + y + nums[b + 1] + nums[b + 2] > target) break;
                    if (x + y + nums[n - 1] + nums[n - 2] < target) continue;
                    int c = b + 1, d = n - 1;
                    while (c < d) {
                        long long s = x + y + nums[c] + nums[d];
                        if (s < target) c += 1;
                        else if (s > target) d -= 1;
                        else {
                            ans.push_back({(int)x, (int)y, nums[c], nums[d]});
                            for (c ++ ; c < d && nums[c] == nums[c - 1]; c ++ );
                            for (d -- ; c < d && nums[d] == nums[d + 1]; d -- );
                        }
                    }  
                }
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 时间复杂度: O ( n 3 ) O(n^3) O(n3)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    1.5 统计和小于目标的下标对数目

    Leetcode 2824

    class Solution:
        def countPairs(self, nums: List[int], target: int) -> int:
            nums.sort()
            n = len(nums)
            l, r = 0, n - 1
            ans = 0
            while l < r:
                if nums[l] + nums[r] < target:
                    ans += r - l
                    l += 1
                else:
                    r -= 1
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    class Solution {
    public:
        int countPairs(vector<int>& nums, int target) {
            int n = nums.size();
            sort(nums.begin(), nums.end());
            int l = 0, r = n - 1, ans = 0;
            while (l < r) 
                if (nums[l] + nums[r] < target)
                    ans += r - l, l += 1;
                else r -= 1;
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    1.6 有效三角形的个数

    Leetcode 611

    class Solution:
        def triangleNumber(self, nums: List[int]) -> int:
            nums.sort()
            n = len(nums)
            ans = 0
            for k in range(2, n):
                c = nums[k]
                l, r = 0, k - 1
                while l < r:
                    if nums[l] + nums[r] > c:
                        ans += r - l
                        r -= 1
                    else:
                        l += 1
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    class Solution {
    public:
        int triangleNumber(vector<int>& nums) {
            sort(nums.begin(), nums.end());
            int n = nums.size();
            int ans = 0;
            for (int k = 2; k < n; k ++ ) {
                int c = nums[k];
                int l = 0, r = k - 1;
                while (l < r) 
                    if (nums[l] + nums[r] > c)
                        ans += r - l, r -= 1;
                    else l += 1;
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    2、相向双指针 2

    2.1 盛最多水的容器

    Leetcode 11

    关于指针的移动:

    • 如果移动指向高度比较高的指针,由于容器的面积取决于 m i n ( h e i g h t [ l ] ,   h e i g h t [ r ] ) min(height[l], \ height[r]) min(height[l], height[r]),因此不管移动指针之后所遇到的墙体高度是否会更好或者更矮,但是由于容器的底边长度始终减一,因此容器的面积只会变得更小!
    • 如果移动指向高度比较低的指针,那么它可能会遇到高度更高的墙体,整个容器面积才有可能更大。
      因此,只有移动只想高度比较低的指针,才有使面积变得更大的机会。
    class Solution:
        def maxArea(self, height: List[int]) -> int:
            ans = l = 0
            r = len(height) - 1
            while l < r:
                area = (r - l) * min(height[l], height[r])
                ans = max(ans, area)
                if height[l] < height[r]:
                    l += 1
                else:
                    r -= 1
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    class Solution {
    public:
        int maxArea(vector<int>& height) {
            int ans = 0, l = 0, r = height.size() - 1;
            while (l < r) {
                int area = (r - l) * min(height[l], height[r]);
                ans = max(area, ans);
                if (height[l] < height[r]) l += 1;
                else r -= 1;
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    2.2 接雨水

    Leetcode 42

    这个题目关于单调栈的解法建议看:题解链接

    解法一:前后缀分解

    class Solution:
        def trap(self, height: List[int]) -> int:
            n = len(height)
            pre_max = [0] * n
            pre_max[0] = height[0]
            for i in range(1, n):
                pre_max[i] = max(height[i], pre_max[i - 1])
            
            suf_max = [0] * n
            suf_max[-1] = height[-1]
            for i in range(n - 2, -1, -1):
                suf_max[i] = max(height[i], suf_max[i + 1])
    
            ans = 0
            for h, pre, suf in zip(height, pre_max, suf_max):
                ans += min(pre, suf) - h
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    class Solution {
    public:
        int trap(vector<int>& height) {
            int n = height.size();
            vector<int> pre_max(n);
            pre_max[0] = height[0];
            for (int i = 1; i < n; i ++ )
                pre_max[i] = max(height[i], pre_max[i - 1]);
            
            vector<int> suf_max(n);
            suf_max[n - 1] = height[n - 1];
            for (int i = n - 2; i >= 0; i -- )
                suf_max[i] = max(height[i], suf_max[i + 1]);
            
            int ans = 0;
            for (int i = 0; i < n; i ++ ) 
                ans += min(pre_max[i], suf_max[i]) - height[i];
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    解法二:双指针

    class Solution:
        def trap(self, height: List[int]) -> int:
            ans = l = pre_max = suf_max = 0
            r = len(height) - 1
            while l < r:
                pre_max = max(pre_max, height[l])
                suf_max = max(suf_max, height[r])
                if pre_max < suf_max:
                    ans += pre_max - height[l]
                    l += 1
                else:
                    ans += suf_max - height[r]
                    r -= 1
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    class Solution {
    public:
        int trap(vector<int>& height) {
            int l = 0, ans = 0, pre_max = 0, suf_max = 0, r = height.size() - 1;
            while (l < r) {
                pre_max = max(pre_max, height[l]);
                suf_max = max(suf_max, height[r]);
                if (pre_max < suf_max)
                    ans += pre_max - height[l], l += 1;
                else ans += suf_max - height[r], r -= 1;
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    解法三:单调栈

    注意:一个凹槽由三个位置决定【最左边( h e i g h t [ l e f t ] height[left] height[left]),中间( b o t t o m h bottom_h bottomh),最右边( h h h)】

    class Solution:
        def trap(self, height: List[int]) -> int:
            ans = 0
            st = []
            for i, h in enumerate(height):
                while st and h >= height[st[-1]]:  # 表示可以形成一个凹槽
                    bottom_h = height[st.pop()]    # 弹出栈顶元素并赋值给bottom_h
                    if not st:                     # 没有左边界
                        break
                    left = st[-1]
                    dh = min(height[left], h) - bottom_h  # 高度差
                    ans += dh * (i - left - 1)
                st.append(i)
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    class Solution {
    public:
        int trap(vector<int>& height) {
            int ans = 0;
            stack<int> st;
            for (int i = 0; i < height.size(); i ++ ) {
                while (!st.empty() && height[i] >= height[st.top()]) {
                    int bottom_h = height[st.top()];
                    st.pop();
                    if (st.empty()) break;
                    int left = st.top();
                    int dh = min(height[left], height[i]) - bottom_h;
                    ans += dh * (i - left - 1);
                }
                st.push(i);
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    另一篇题解的单调栈代码:

    class Solution {
    public:
        int trap(vector<int>& height) {
            int ans = 0;
            stack<int> st;
            int cur = 0;
            while (cur < height.size()) {
                while (!st.empty() && height[cur] > height[st.top()]) {
                    int h = height[st.top()];
                    st.pop();
                    if (st.empty()) break;
                    int distance = cur - st.top() - 1;
                    int min_h = min(height[st.top()], height[cur]);
                    ans += distance * (min_h - h);
                }
                st.push(cur);
                cur ++ ;
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( m i n ( U , n ) ) O(min(U, n)) O(min(U,n)),其中 U = m a x ⁡ ( h e i g h t ) − m i n ⁡ ( h e i g h t ) + 1 U=max⁡(height)−min⁡(height)+1 U=max(height)min(height)+1

    3、同向双指针:滑动窗口(区间大小可变)

    3.1 长度最小的子数组

    Leetcode 209

    这里能够使用双指针是因为 w h i l e while while 条件中是满足单调性的

    class Solution:
        def minSubArrayLen(self, target: int, nums: List[int]) -> int:
            n = len(nums)
            ans = inf
            s = left = 0
            for right, x in enumerate(nums):
                s += x
                while s >= target:
                    ans = min(ans, right - left + 1)
                    s -= nums[left]
                    left += 1
            return ans if ans <= n else 0
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    class Solution {
    public:
        int minSubArrayLen(int target, vector<int>& nums) {
            int n = nums.size(), ans = n + 1, s = 0, left = 0;
            for (int right = 0; right < n; right ++ ) {
                s += nums[right];
                while (s >= target) {
                    ans = min(ans, right - left + 1);
                    s -= nums[left ++ ];
                }
            }
            return ans <= n ? ans : 0;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    3.2 乘积小于 K 的子数组

    Leetocde 713

    class Solution:
        def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
            if k <= 1: return 0
            ans = l = 0
            prod = 1
            for r, x in enumerate(nums):
                prod *= x
                while prod >= k:
                    prod /= nums[l]
                    l += 1
                ans += r - l + 1
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    class Solution {
    public:
        int numSubarrayProductLessThanK(vector<int>& nums, int k) {
            if (k <= 1) return 0;
            int n = nums.size(), ans = 0, prod = 1, left = 0;
            for (int right = 0; right < n; right ++ ) {
                prod *= nums[right];
                while (prod >= k) prod /= nums[left ++ ];
                ans += right - left + 1;
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    3.3 无重复字符的最长字串

    Leetcode 3

    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            ans = l = 0
            w = set()
            for r, c in enumerate(s):
                while c in w:
                    w.remove(s[l])
                    l += 1
                w.add(c)
                ans = max(ans, r - l + 1)
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    python 另一个版本,效率比上面一个略微差一点:

    class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            ans = 0
            cnt = Counter()
            left = 0
            for right, c in enumerate(s):
                cnt[c] += 1
                while cnt[c] > 1:
                    cnt[s[left]] -= 1
                    left += 1
                ans = max(ans, right - left + 1)
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int n = s.size(), ans = 0, l = 0;
            unordered_set<char> w;
            for (int r = 0; r < n; r ++ ) {
                char c = s[r];
                while (w.count(c)) w.erase(s[l ++ ]);
                w.insert(c);
                ans = max(ans, r - l + 1);
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 128 ) ≈ O ( 1 ) O(128) \approx O(1) O(128)O(1)

    3.4 最大连续1的个数 III

    Leetcode 1004

    注意思路!!!

    class Solution:
        def longestOnes(self, nums: List[int], k: int) -> int:
            ans = left = cnt0 = 0  # cnt0 用于统计窗口内部0的个数
            for right, x in enumerate(nums):
                cnt0 += 1 - x
                while cnt0 > k:
                    cnt0 -= 1 - nums[left]
                    left += 1
                ans = max(ans, right - left + 1)
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    class Solution {
    public:
        int longestOnes(vector<int>& nums, int k) {
            int n = nums.size(), l = 0, ans = 0, cnt0 = 0;
            for (int r = 0; r < n; r ++ ) {
                cnt0 += 1 - nums[r];
                while (cnt0 > k) 
                    cnt0 -= 1 - nums[l ++ ];
                ans = max(ans, r - l + 1);
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    3.5 替换子串得到平衡字符串

    Leetcode 1234

    如果在 待替换子串(即滑动窗口) 之外的任意字符的出现次数超过 m = n 4 m=\frac{n}{4} m=4n,那么无论怎么替换,都无法使这个字符的出现次数等于 m m m

    反过来说,如果在待替换子串之外的任意字符的出现次数都不超过 m m m,那么可以通过替换,使 s s s 为平衡字符串,即每个字符的出现次数均为 m m m

    class Solution:
        def balancedString(self, s: str) -> int:
            cnt, m = Counter(s), len(s) // 4
    
            # 用于判断可迭代对象中的所有元素是否都为真
            if all(cnt[x] == m for x in "QWER"): 
                return 0
                
            ans, left = inf, 0
            for right, c in enumerate(s):
                cnt[c] -= 1
                while all(cnt[x] <= m for x in "QWER"):
                    ans = min(ans, right - left + 1)
                    cnt[s[left]] += 1
                    left += 1
                    
            return ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    class Solution {
    public:
        int balancedString(string s) {
            int n = s.length(), m = n / 4, cnt['X']{};
            for (char c: s) cnt[c] ++ ;
            if (cnt['Q'] == m && cnt['W'] == m && cnt['E'] == m && cnt['R'] == m)
                return 0;
            int ans = n, l = 0;
            for (int r = 0; r < n; r ++ ) {
                cnt[s[r]] -- ;
                while (cnt['Q'] <= m && cnt['W'] <= m && cnt['E'] <= m && cnt['R'] <= m) {
                    ans = min(ans, r - l + 1);
                    cnt[s[l ++ ]] ++ ;
                }
            }
            return ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 时间复杂度: O ( C N ) O(CN) O(CN),其中 C = 4 C=4 C=4 N N N 为字符串 s s s 的长度
    • 空间复杂度: O ( C ) O(C) O(C)

    3.6 将 x 减到 0 的最小操作数

    Leetcode 1658

    逆向思维

    将原问题转换为求解数组中最长的子数组,使得子数组的元素和为 s − x s - x sx,其中 s s s 表示整个数组的和。

    class Solution:
        def minOperations(self, nums: List[int], x: int) -> int:
            target = sum(nums) - x
            if target < 0: return -1
            ans = -1  # 存储长度
            left = s = 0  # s 存储窗口内的和
            for right, x in enumerate(nums):
                s += x
                while s > target:
                    s -= nums[left]
                    left += 1
                if s == target:
                    ans = max(ans, right - left + 1)
            return -1 if ans < 0 else len(nums) - ans
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    class Solution {
    public:
        int minOperations(vector<int>& nums, int x) {
            int target = accumulate(nums.begin(), nums.end(), 0) - x;
            if (target < 0) return -1;
            int ans = -1, l = 0, sum = 0, n = nums.size();
            for (int r = 0; r < n; r ++ ) {
                sum += nums[r];
                while (sum > target) sum -= nums[l ++ ];
                if (sum == target) ans = max(ans, r - l + 1);
            }        
            return ans < 0 ? -1 : n - ans;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)
  • 相关阅读:
    HDFS、Yarn、Hive…MRS中使用Ranger实现权限管理全栈式实践
    Spring系列文章:面向切面编程AOP
    软件架构之前后端分离架构&服务器端高并发演进之路
    nSoftware.PowerShell.Server.2020
    typora+python打造舒适的文档写作环境
    示例:WPF中绑定枚举到ComboBox的方式
    梦开始的地方——C语言指针练习题
    【JVM技术专题】精心准备了一套JVM分析工具的锦囊「JConsole补充篇」
    Java无锁并发
    大模型实战—大模型web服务部署
  • 原文地址:https://blog.csdn.net/qq_34696503/article/details/134050745