写在前面

最近力扣刷的有点上瘾，做完一题还想再做一题，每次AC都非常舒服，比刷抖音什么的爽多了，但是过程总是痛苦并快乐的。其实自己还是小白的水平，做什么题永远想到的就是暴力，什么算法什么数据结构都是后面实在没招了才想一想，差距还是非常大的。
最近做题已经遇上了一些瓶颈，比如根本想不到，或者这个算法根本没学过就做不了，最痛苦的就是辛辛苦苦暴力写完了，提交的时候显示超时，这无疑就是对暴力的否定。我也知道一直写暴力代码一点都提升不了，所以就有了这篇《经典算法合集》，我发现算法是可以积少成多练会的，因为算法很固定，知道就是知道，不知道怎么都写不出来，看题解的时候看到一个新算法就醍醐灌顶，真的是学到了很多。因此再次记录下来，方便总结和查阅。

滑动窗口

算法核心

当你需要在一个序列中寻找子序列或子数组的最优解或满足某些条件的解时，滑动窗口算法是一个非常有用的技巧。它通常用于解决子串或子数组相关的问题。滑动窗口算法的核心思想是维护一个窗口，通过移动窗口的起始和结束位置，来逐步遍历整个序列。

下面是滑动窗口算法的基本步骤：
1、初始化窗口的左右边界，通常将左边界设为序列的起始位置，右边界设为左边界加上窗口大小。
2、开始移动窗口，根据问题的要求，可能需要增加左边界或右边界，以满足特定条件。
3、在每次窗口移动后，检查窗口中的子序列或子数组是否满足问题的条件或最优解的要求。
4、如果满足条件，记录答案或更新最优解。
5、重复步骤2和步骤3，直到窗口的右边界达到序列的末尾。

滑动窗口算法的关键在于如何移动窗口的左右边界和如何检查窗口中的子序列。这取决于具体的问题。以下是一些滑动窗口算法应用的示例：
最小窗口子串：在一个字符串中找到包含指定字符集合的最短子串。
最长无重复字符子串：在一个字符串中找到最长的子串，其中没有重复的字符。
固定大小的子数组的平均值：在一个数组中找到固定大小的子数组，其平均值满足某个条件。
最大子数组和：找到一个数组中和最大的连续子数组。

滑动窗口算法通常能够在O(N)的时间复杂度内解决这些问题，其中N是序列的长度。这使得它成为解决子序列相关问题的高效方法。

模板

算法大佬提供的滑动窗口典型模板，还是很有收获的
滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。

模板的整体思想是：
1、定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；
2、第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和/计数；
3、第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和/计数；
4、在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max(res, 当前区间的长度) 。
5、right 指针每次向右移动一步，开始探索新的区间。

模板中的 sums 需要根据题目意思具体去修改，本题是求和题目因此把sums 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sums 。
另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间 [left, right]不符合题意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findSubArray(nums):
    N = len(nums) # 数组/字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间[left, right]，闭区间
    sums = 0 # 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
    res = 0 # 保存最大的满足题目要求的 子数组/子串 长度
    while right < N: # 当右边的指针没有搜索到 数组/字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字/字符的求和/计数
        while 区间[left, right]#不符合题意: # 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从counter中减少left位置字符的求和/计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组/子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res

典型例题

力扣643、子数组最大平均数

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：
输入：nums = [5], k = 1
输出：5.00000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public double findMaxAverage(int[] nums, int k) {

        // 滑动窗口
        // 题目给出长度为k，保持双指针之间的长度固定

        int sum = 0;
        int n = nums.length;
        // 计算第一个窗口，以后的窗口只在这个窗口上减去一个旧的，添加一个新的
        for(int i = 0; i < k; i++){
            sum += nums[i];
        }
        // 用第一个窗口的和初始化max
        int maxSum = sum;
        // 以后的窗口从k开始
        for(int i = k; i < n; i++){
            // 用第一个（上一个）窗口的和减去最后一个值，然后新增一个值，就是下一个窗口
            sum = sum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, sum);
        }
        return 1.0 * maxSum / k;
    }
}

力扣1456、字符串元音最大数目

给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。

自己写的时候超时了，当时想的是滑动窗口但是时间复杂度还是O(n^2)，真的懊恼，还是没有明白滑动窗口的精髓,下面是滑动窗口变种

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
class Solution {
    public int maxVowels(String s, int k) {
        //滑动窗口典型题
        int n = s.length();
        //维护最大的元音数目
        int ans = 0;
        //每次循环维护的元音数目
        int count = 0;
        //滑头窗口头,尾
        int left = 0, right = 0;
        while(right < n) {
            char temp = s.charAt(right);
            if(temp=='a'||temp=='e'||temp=='i'||temp=='o'||temp=='u') {
                count++;
            }
            right++;
            if(right - left == k) {
                //此时把count和ans比较找到最大值
                ans = Math.max(ans, count);
                //处理滑动窗口的头，如果是元音那么count要减一
                char c = s.charAt(left);
                if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u') {
                    count--;
                }
                //无论如何窗口都要往右移不然就超过了k
                left++;
            }
        }
        return ans;
    }
}

官方解答，其实和力扣643的一样了,这两道题让我明白了要想使用滑动窗口就必须把第一个窗口的值好好利用起来，或者说先算出第一个窗口，后面加减起来就很方便了，时间复杂度也降到了O(|s|)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxVowels(String s, int k) {
        int n = s.length();
        int vowel_count = 0;
        for (int i = 0; i < k; ++i) {
            vowel_count += isVowel(s.charAt(i));
        }
        int ans = vowel_count;
        for (int i = k; i < n; ++i) {
            vowel_count += isVowel(s.charAt(i)) - isVowel(s.charAt(i - k));
            ans = Math.max(ans, vowel_count);
        }
        return ans;
    }

    public int isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ? 1 : 0;
    }
}

力扣1208、尽可能让字符串相等

记录一下第一次完全独立写出滑动窗口！！！基本使用已经刻在脑子里了

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
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        //这题一定可以自己做出来！！！
        //滑动窗口标准要用的变量
        int n = s.length();
        //count每次窗口的累加值，ans维护最大值
        int count = 0, ans = 0;
        //滑动窗口左右边界
        int left = 0, right = 0;
        while(right < n) {
            //根据提议累加count
            count += Math.abs(s.charAt(right) - t.charAt(right));

            //如果右边界加上后不满足题意，要减去原来超出的值，并且此时就要被迫移动左边界指针
            while(count > maxCost) {
                count = count - Math.abs(s.charAt(left) - t.charAt(left));
                left++;
            }
            //记录最大值
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
}

力扣1493、删一个元素找到最长1字串长度

给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。

提示 1：
输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

示例 2：
输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。

示例 3：
输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int longestSubarray(int[] nums) {
        //滑动窗口变形题,学会就是秒杀题啦，开心
        int n = nums.length;
        int ans = 0, res = 0;
        int left = 0, right = 0;

        while(right < n) {
            if(nums[right] == 0) {
                res++;
            }

            while(res > 1) {
                if(nums[left++] == 0) {
                    res--;
                }
            }
            //删除零所以就不用加一啦
            ans = Math.max(ans, right - left);
            right++;
        }
        return ans;
    }
}

前缀和

算法核心

前缀和算法（Prefix Sum）是一种用于高效处理数组区间和的技巧。它通过在预处理阶段计算累积和，并将这些累积和存储在额外的数组中，以便在之后的查询中能够以常数时间计算出任意区间的和。前缀和通常用于解决需要频繁查询数组区间和的问题。

下面是前缀和算法的基本思想和步骤：

预处理阶段：遍历原始数组，计算每个位置（索引）之前的所有元素的和，将这些和存储在一个新的数组中。这个新数组被称为前缀和数组。
查询阶段：一旦前缀和数组构建完成，你可以以常数时间计算出任意区间的和，而不需要重新计算。对于一个区间 [i, j] 的和，只需使用前缀和数组中的值计算：prefixSum[j] - prefixSum[i-1]，其中 prefixSum[i-1] 是区间 [0, i-1] 的和（如果i为0，可以省略）。

前缀和算法适用于解决多种问题，例如：
子数组区间和查询：在一个数组中查询给定区间 [i, j] 内的元素和。
连续子数组的和等于给定值：在一个数组中查找连续子数组，其和等于给定值。
计算二维矩阵区域和：在一个二维矩阵中计算给定区域的和，通过构建二维前缀和数组。

前缀和算法的主要优势在于它的查询效率非常高，通常能在O(1)的时间复杂度内完成。然而，构建前缀和数组需要额外的O(N)的空间，因此在内存有限的情况下需要权衡空间和时间的利用。

下面是一个简单的示例，演示如何使用前缀和算法计算数组中给定区间的和：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class PrefixSumExample {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        
        // 预处理，构建前缀和数组
        int n = nums.length;
        int[] prefixSum = new int[n];
        prefixSum[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
        
        // 查询区间 [2, 5] 的和
        int left = 2;
        int right = 5;
        int sum = (left == 0) ? prefixSum[right] : prefixSum[right] - prefixSum[left - 1];
        System.out.println("区间 [" + left + ", " + right + "] 的和为: " + sum);
    }
}

典型例题

力扣1732、找到最高海拔

有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。
给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。

示例 1：
输入：gain = [-5,1,5,0,-7]
输出：1
解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。

示例 2：
输入：gain = [-4,-3,-2,-1,4,3,2]
输出：0
解释：海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int largestAltitude(int[] gain) {
        int res = 0, height = 0;
        for (int i = 0; i < gain.length; i++) {
            height += gain[i];
            res = Math.max(res, height);
        }
        return res;
    }
}

力扣724、寻找数组的中心下标

给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

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
class Solution {
    public int pivotIndex1(int[] nums) {
        int total = Arrays.stream(nums).sum();
        int sum = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }

    //下面是自己写的哈哈
    public int pivotIndex2(int[] nums) {
        //计算前缀和和后缀和两个数组下标
        int n = nums.length;
        int sum1 = 0;
        int sum2 = 0;
        int[] hou = new int[n];
        int[] qian = new int[n];
        for (int i = 0,j = n - 1; i < n && j >= 0; i++,j--) {
            sum1 += nums[i];
            sum2 += nums[j];

            qian[i] = sum1;
            hou[j] = sum2;
        }
        for (int i = 0; i < n; i++) {
            if(qian[i] == hou[i]) {
                return i;
            }
        }
        if(hou[1] == 0 ) {
            return 0;
        } else if (qian[n - 2] == 0) {
            return n - 1;
        } else {
            return -1;
        }
    }
}