labuladong算法笔记｜滑动窗口算法

灵神｜【题单】滑动窗口与双指针（定长/不定长/至多/至少/恰好/单序列/双序列/三指针）

今天重新整理滑动窗口的题目，开始参考灵神分享的题单并结合推荐的插件来做题。

滑动窗口主要的思路就是，在右侧添加窗口，在左边缩小窗口。

一、定长滑动窗

1.1、基础

1456. 定长子串中元音的最大数目 （20241218）

太强了，一看题解就懂的那种。

这个题目涉及的是定长的窗口，先往里面填充数据，在更新答案，然后在将数据剔除。

class Solution {
    public int maxVowels(String S, int k) {
        // 进入窗口、更新答案、离开窗口
        char[] s = S.toCharArray();
        int ans = 0;
        int vowel = 0;
        for(int i= 0;i<s.length;i++){
            // 进入窗口
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u'){
                vowel++;
            }
            if(i < k-1){ // i < k-1的时候就一直往里面添加
                continue;
            }
            // 更新答案
            ans = Math.max(ans, vowel);
            // 离开窗口
            char o = s[i-k+1];  // 这里i-k+1就是窗口第一个数据的下标
            if(o == 'a' || o == 'e' || o == 'i' || o == 'o' || o == 'u'){
                vowel--;
            }
        }
        return ans;
    }
}

这里我看下为什么i-k+1表示的是窗口的第一个数据的下标？

因为使用了一个位置来进行数据交换，中间是有两个数据是确定的，就是 k-1个数据是确定的，那么窗口的第一数据的下标就是 i - (k-1) ，转化就是 i - k + 1就表示窗口里面第一个数据的下标。

643. 子数组最大平均数 I（20241218）

使用模版求解。

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double ans = Integer.MIN_VALUE; // 因为求的是最大的平均值，这里要定义最小，不能定义成0.0
        double sum = 0.0;
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            if(i < k-1){
                continue;
            }   
            ans = Math.max(ans, sum/ k);
            sum -= nums[i-k+1];
        }
        return ans;
    }
}

...

1343. 大小为 K 且平均值大于等于阈值的子数组数目（20241218）

使用模版求解。

2090. 半径为 k 的子数组平均值（20241219）

这个题目还是有些是值得注意的。

题目给出的窗口是以i为中心，k为半径的窗口， 里面有一些细节，像是窗口的长度len 等于2 * k + 1， 循环的时候还是循环[0, nums.length)，

对应的存放数据的下标是i-k，最前面需要移除元素的下标是i-len+1，相当于i - 2*k。

Arrays.fill(ans, -1);将所有的元素都赋值成为-1.

class Solution {
    public int[] getAverages(int[] nums, int k) {
        
        int[] ans = new int[nums.length];
        Arrays.fill(ans, -1);
   
        int sum = 0;
        int len = 2 * k + 1;
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            if(i < len - 1){  // 这里就控制了下标小于len-1的值不会向下流转
                continue;
            }  
            ans[i-k] = (int)(sum / len);  // 这里就控制了下标最多就是i-k
            sum -= nums[(int)(i-len+1)]; // 是减去最前面的下标的值
        }
        return ans;
        
    }
}

2379. 得到 K 个黑块的最少涂色次数（20241219）

标准的模版解法，只是其中转化了一下思路，求窗口里面最多的黑色块x，最后用窗口的长度减去最多的黑色块x得到答案。

在移除时候的下标是 i - (k-1) ，也就是 i-k=1；

1461. 检查一个字符串是否包含所有长度为 K 的二进制子串（20241219）

子串：连续的字符组成的字符串，一个长度为n的字符串所拥有的子串个数为： n * (n-1)/ 2 + 1，（子串是连续的）

子序列：在原来的序列中找出一部分元素组成的序列（子序列是不连续的）

长度为k的只包含字符'0'和字符'1'的子串个数等于2^k。

开始想的是把所有长度为k的为包含0和1字符的子串都求出来，然后在求出来s的所有子串进行对比。

但是可以对比这两个子串的个数来求解这一道题，肯定是 2^k >= sub(s)， 当两者想等的时候条件成立，如果2^k > sub(s)那么必定有一个或者多个子串不在s的子串里面，返回false。

class Solution {
    public boolean hasAllCodes(String S, int k) {
        // 只需要计算长度为k的由1或者0组成的串有多少个 2的k次方
        // 然后找出来s中长度为k的所有子串的个数
        StringBuilder s = new StringBuilder();
        Set<String> set = new HashSet<>();

        char[] chars = S.toCharArray();
        for(int i = 0;i<chars.length;i++){
            s.append(chars[i]);
            if(i < k-1){
                continue;
            }   
            set.add(s.toString());
            
            s.deleteCharAt(0);
        }
        return set.size() == Math.pow(2, k);
    }
}

2841. 几乎唯一子数组的最大和（20241219）

读题就读了半天， 简单来理解有两个条件， 一个是窗口里面的值求和为最大值，二个是窗口里面互不相同的元素的个数要大于等于m。

开始使用Set来做的，但是有一个用例nums = [1,1,1,3], k = 2, m=2 这个过不了，因为到[1, 3] 的时候，前面的1给从集合里面剔除掉了，导致出现了错误。

后面换成Map来做，统计每个元素的个数。

class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        long sum = 0;
        long ans = 0;

        for(int i = 0;i<k-1;i++){  // 先统计前面k-1个元素的总和，并添加到map里面
            sum += nums.get(i);
            cnt.merge(nums.get(i), 1, Integer::sum);
        }

        for(int i = k-1;i<nums.size();i++){
            sum += nums.get(i);
            cnt.merge(nums.get(i), 1, Integer::sum);  // 把第k个元素放进去

            if(cnt.size() >= m){  // 判断是否满足第二个条件
                ans = Math.max(ans, sum);
            }

            sum -= nums.get(i-k+1);  // 删除元素操作
            if(cnt.merge(nums.get(i-k+1), -1, Integer::sum) == 0){  // 如果cnt减完之后value等于0的话就把他从map里面删除掉
                cnt.remove(nums.get(i-k+1));
            }
        }
        return ans;
    }
}

2461. 长度为 K 子数组中的最大和（20241219）

子数组 是数组中一段连续非空的元素序列。

子序列 是数组中非连续非空元素的序列。

这个题目和上面一个题目类似，都是在统计窗口元素和的同时，维护窗口中元素出现的次数问。

1423. 可获得的最大点数（20241219）

这个题很容易就会想到用双指针的思路来解，但是有会面临一个问题，就是左边的值和右边的值一样的情况下要怎么处理，所以换个思路思考：

拿走k张牌之后，剩下n-k张牌，这里的n是cardPoints的长度，那么剩下来的牌必然是连续的，想要求拿走的牌的最大点数，其实可以逆向思维思考，求剩下的连续的最小和，所以题目就变成了： 求窗口长度为n-k的最小和，然后用总和见到最小和就是题目所求的。

class Solution {
    public int maxScore(int[] cardPoints, int k) {
        
        k = cardPoints.length - k;
        
        long sum = 0;
        long ans = Integer.MAX_VALUE;
        long total = 0;
        for(int i = 0;i<cardPoints.length;i++){
            total += cardPoints[i];
        }
        if(k == 0){
            return (int)total;
        }

        for(int i = 0;i<cardPoints.length;i++){
            sum += cardPoints[i];
            
            if(i < k-1){
                continue;
            }
            ans = Math.min(ans, sum);
            sum -= cardPoints[i-k+1];
        }
        return (int)(total - ans);
        
    }
}

1652. 拆炸弹（20241220）

我悟到了

仔细阅读题目之后，我们都明白了，当k=0时全为1；当k>0的时候，值等于当前下标后面k个元素的和；当k<0时，值等于当前下标前面k个元素的和。

可以看出来，定长窗口都是向右移动的，重要的是确定第一个窗口的位置在哪里， 窗口的长度都是k。

当k>0的时候，我们很容易得到第一个窗口是 [1, k+1)（左端点为参照），当k<0时，我们也能够得到窗口的下标 [n - |k|, n)（右端点为参照）。

还需要解决的一个问题就是添加元素的下标和剔除元素的下标？

我们统一第一个窗口右侧下标为r， 那么窗口左侧下标就是r-|k|， 然后求余数分别就是[r%n, (r-|k|) % n]。

class Solution {
    public int[] decrypt(int[] code, int k) {
        int n = code.length;
        int[] ans = new int[n];

        // r表示第一个窗口的右边下标
        // 所以构建出来一个长度为k，窗口下标为[r-1, r]的窗口
        int r = k> 0? k+1: n;  
        
        k = Math.abs(k);
        int s = 0;

        for(int i = r-k;i<r;i++){
            s += code[i];  // 计算ans[0]
        }
        for(int i = 0;i<n;i++){ 
            ans[i] = s;
            s += code[r % n] - code[(r-k) %n];
            r++;  // 每次i向后移动一位，r也向后移动一位
        }
        return ans;
        
    }
}

1297. 子串的最大出现次数（20241220）

满足两个条件：1 子串不同字符个数小于maxLetters；2 子串长度大于minSize，小于maxSize

要出现次数最多，那么子串的长度就尽量短，所以可以转化成固定窗口长度为minSize的滑动窗口题目

结合灵神定长滑动窗口的思路解题。

补充：求map最大的value -> map.values().stream().max(Integer::compareTo).orElse(0);

class Solution {
    public static int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        // 满足两个条件：1 不同字符个数小于maxLetters；2 子串长度大于minsize，小于maxsize
        // 要出现次数最多，那么子串的长度就尽量短，所以可以转化成固定窗口长度为minSize的滑动窗口题目

        // 用来统计子串中不同字符的个数
        Map<Character, Integer> cnt = new HashMap<>();
        // 用来记录满足条件的子串出现的次数
        Map<String, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        // 子串
        StringBuilder str = new StringBuilder();
        for(int i = 0;i<chars.length;i++){
            // in
            cnt.merge(chars[i], 1, Integer::sum);
            str.append(chars[i]);
            if(i< minSize - 1){
                continue;
            }
            //
            if(cnt.size() <= maxLetters){
                map.merge(str.toString(), 1, Integer::sum);
            }
            // out
            str.deleteCharAt(0);

            if(cnt.merge(chars[i-minSize+1], -1, Integer::sum) == 0){
                cnt.remove(chars[i-minSize+1]);
            }
        }
        return map.values().stream().max(Integer::compareTo).orElse(0);
    }
}

二、不定长滑动窗口

不定长滑动窗口主要分为三类：求最长子数组，求最短子数组，以及求子数组的个数。

2.1、求最长或最大

3. 无重复字符的最长子串（20241223）

主要的思路就是把右侧的数据添加进来，然后判断是否已经存在了，如果已经存在了，那就缩小左边的窗口，直到没有重复的元素；如果不存在，就将元素添加到窗口里面。

class Solution {
    public int lengthOfLongestSubstring(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int ans = 0;
        int left = 0;  // 窗口左端点
        boolean[] has = new boolean[128];       
        for(int right=0;right<n;right++){
            // 窗口右端点添加一个字符，判断是不是已经存在了
            while(has[s[right]]){ // 如果存在了，就缩小窗口
                has[s[left]] = false;
                left++;  // 缩小窗口
            }
            has[s[right]] = true;  // 否则就更新
            ans = Math.max(ans, right - left + 1);  // 然后更新答案
        }
        return ans;
    }
}

...

3090. 每个字符最多出现两次的最长子字符串（20241223）

字符不重复解题思路相同， 只需要改变判断次数的代码。

有一个可以优化的思路，就是之前是用的Map<Character, Integer> has = new HashMap<>();来判断出现次数的；可以直接用数组来判断int[] has = new int[26];因为只有26个小写的英文字符。

class Solution {
    public int maximumLengthSubstring(String S) {
        char[] s = S.toCharArray();
        int ans = 0;
        int left = 0;

        int[] cnt = new int[26]; // 26个字母，用数组来保存26个小写字符

        for(int i=0;i<s.length;i++){
            int b = s[i] - 'a';
            cnt[b]++;
            while(cnt[b] > 2){
                cnt[s[left] - 'a']--;
                left++;
            }
            ans = Math.max(ans, i - left + 1);
        }
        return ans;       
    }
}

1493. 删掉一个元素以后全为 1 的最长子数组（20241223）

因为求删除一个元素后全为1的最长子数组，求包含一个0，其他全为1的最长子数组。

当nums全为1的时候也同样满足。

class Solution {
    public int longestSubarray(int[] nums) {
        // 求包含一个0的最长子串
        int ans= 0 ;
        int cnt = 0;
        int left = 0;

        for(int right = 0;right<nums.length;right++){
            // 先添加
            if(nums[right] == 0){
                cnt++;
            }
            // 判断条件
            while(cnt > 1){
                if(nums[left] == 0){
                    cnt--;
                }
                left++;  // 把left++放到这里是因为，如果是1的时候cnt不做处理，直接跳过
            }
            // 更新答案
            ans = Math.max(ans, right-left+1);
        }
        return ans-1;
    }
}

1208. 尽可能使字符串相等（20241224）

对于这个题目，我甚至连题目都没有看懂，但是在看到下面题解关于题目的讲解的时候，我就明白了。

在看到costs数组等于[1,1,1,2]的时候，在结合maxCost = 3的时候，解题思路就明朗了，就是先将两个字符穿转化的开销维护起来， 在使用灵神不定长滑动窗口的解题模板，很快就能解决了。

看来理解题目对于解题是相当重要的。

2730. 找到最长的半重复子字符串（20241224）

这个题题目理解起来还是比较容易的，就是求最多只有一对相邻字符的最大的子串。

定义same表示相同字符的对数，移动right， 当same>1的时候，就移动left，直到left和left-1对应的值相同，然后把same置为1。

这里容易陷入一个误区，就是可能会统计每个字符出现的次数，因为相同字符的对数不一样的话，处理的逻辑也不一样。

class Solution {
    public int longestSemiRepetitiveSubstring(String S) {
        char[] s = S.toCharArray();
        int same = 0;  // 记录相同字符对数出现的次数
        int ans =1;
        int left = 0;
        
        for(int right = 1;right<s.length;right++){
            if(s[right] == s[right-1]){
                same++;
            }
            if(same > 1){
                left++;
                while(s[left] != s[left-1]){
                    left++;
                }
                same = 1;
            }
            ans = Math.max(ans, right-left+1);
        }
        return ans;
    }
}

904. 水果成篮（20241225）

喵的题解都看不懂的题

用哈希表来处理要好容易理解一点。

class Solution {
    public static int totalFruit(int[] fruits) {
        int ans = 0;
        int left = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int right=0;right<fruits.length;right++){
            // 添加数据到cnt里面
            cnt.merge(fruits[right], 1, Integer::sum);

            while(cnt.size() > 2){
                // 当size大于2的时候，就把左指针的数据remove掉
                cnt.merge(fruits[left], -1, Integer::sum);
                if(cnt.get(fruits[left]) == 0){
                    cnt.remove(fruits[left]);
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

还需要理解一个就是， ++i和i++的区别。

public class Q904 {
    public void test2(){
        int a = 1,b = 1, c = 1, d = 1;
      	// ++a 表示先运算a = a+1， 在执行a+1 == 1
        System.out.println(++a == 1);
      	// b++ 表示先运算 b == 1，然后在执行b = b+1
        System.out.println(b++ == 1);
        // true
        System.out.println(1 == c++);
        // false
        System.out.println(1 == ++d);
    }
}

1695. 删除子数组的最大得分（20241226）

题目的意思就是：求最大元素只出现一次的子数组的和。不定长滑动窗口求解。

class Solution {
    public int maximumUniqueSubarray(int[] nums) {
        // 求所有元素只出现一次的最大数组和
        int sum = 0;
        int left = 0;
        int ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int right = 0;right<nums.length;right++){
            // 添加
            cnt.merge(nums[right], 1, Integer::sum);
            sum += nums[right];
            
            while(cnt.get(nums[right]) >= 2){
                if(cnt.merge(nums[left], -1, Integer::sum) == 0){
                    cnt.remove(nums[left]);
                }
                sum -= nums[left];
                left++;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

2958. 最多 K 个重复元素的最长子数组（20241226）

和上面一题是相同的解决思路，相同的代码这里就不贴了。

刚才考虑到一个问题，就是用map能解决，用int[]数组能解决吗？

用数组可能不行，因为你不知道创建的数组的长度是多少， 给出的1 <= nums[i] <= 10^9, 1 <= nums.length <= 10^5 ，如果创建一个10^5大的数组，那么空间复杂度就非常的高。

2024. 考试的最大困扰度（20241227）

说实话，这个题我是看懂了的，但是就是写不出来。灵神的位运算现在的我还看不懂，后面学到的时候在回过头来看。

题意：求answerKey的一个最长子串，至多包含k个T或者至多包含k个F

滑动窗口

public class Q2024 {
    public static int maxConsecutiveAnswers(String answerKey, int k) {
        char[] s = answerKey.toCharArray();
        int ans = 0;
        int left = 0;
        // 统计T和F的个数
        int[] cnt = new int[2];
        for (int right = 0; right < s.length; right++) {
            // 存入到cnt里面
            cnt[s[right] >> 1 & 1]++;
            // 如果T的个数或者F的个数大于k，这里就是重要的判断
            while (cnt[0] > k && cnt[1] > k) {
                // 就把left位置所在的符号的次数减一
                cnt[s[left++] >> 1 & 1]--;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

1004. 最大连续1的个数 III（20241227）

这个和上面一样的解题思路，确定不满足题意的条件，就是当子数组里面0出现的次数大于k的时候，就需要移动左端窗口了。

解题代码类似：

class Solution {
    public int longestOnes(int[] nums, int k) {
        // nums包含的0不超过k的最长子数组
        int ans = 0;
        int left = 0;
        int[] cnt = new int[2];
        for(int right=0; right<nums.length;right++){
            cnt[nums[right]]++;
            while(cnt[0] > k){
                cnt[nums[left++]]--;
            }
            ans = Math.max(ans, right- left+1);
        }
        return ans;       
    }
}

1658. 将 x 减到 0 的最小操作数（20241227）

逆向思维解这道题，x恰好减到0的最小操作数，可以想成求和为s-x的最长子数组，s表示数组的和。

class Solution {
    public int minOperations(int[] nums, int x) {
        // 求 s - x的最长子数组
        int s = Arrays.stream(nums).sum();
        int t = s - x;
        if (t < 0)
            return -1;
        int ans = -1, left = 0, total = 0;
        for (int i = 0; i < nums.length; i++) {
          	// 添加数据，如果加入之后大于了目标值，就收缩左边窗口，直到小于等于目标值
            total += nums[i];
            while (total > t) {
                total -= nums[left++];
            }
            if (total == t) {
                ans = Math.max(ans, i - left + 1);
            }
        }
      	// 因为ans是s-x的最长子数组，所以需要数组长度-ans才是最终答案。
        return ans == -1 ? -1 : nums.length - ans;
    }
}

2.3、求子数组个数

2.3.1、越短越合法

一般要写ans+=right-left+1;

内层循环结束后，[left, right]这个子数组是满足题目要求的，由于子数组越短，越能满足题目要求，所以除了[left, right], 还有[left+1, right], [left+2, right] ... [right, right]都是满足要求的，也就是说当右端点固定在right时，左端点 在left， left+1...right 的所有子数组都是满足要求的，一共right-left+1个。

713. 乘积小于 K 的子数组（20250820）

Details

给你一个整数数组 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

子数组是连续的数组元素组成的数组。

因为nums[i] >= 1，又需要找到严格小于k的值，（严格小于就是小于，相等都不行）所以当k<=1的时候，没有这样的数组，直接返回0。

数组越长，乘积越大越不满足；反之数组越短，乘积越小，越能满足题目要求。

枚举子数组右端点，[left, right]满足的话， [left+1, right]....[right, right]都是满足的，一共有right-left+1个，加入到答案中。

Java

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) {
            return 0;
        }

        int ans = 0;
        int pord = 1;
        int left = 0;

        for (int i = 0; i < nums.length; i++) {
            // 入
            pord *= nums[i];
            // 只要prod大于k，就要缩小窗口，不只是缩小一次。
            // 出
            while (pord >= k) {
                pord /= nums[left];
                left++;
            }
            // 更新答案
            ans += (i - left + 1);
        }
        return ans;

    }
}

2348. 全 0 子数组的数目（20250820）

Details

给你一个整数数组 nums ，返回全部为 0 的 子数组 数目。

子数组 是一个数组中一段连续非空元素组成的序列。

示例 1：

输入：nums = [1,3,0,0,2,0,0,4]
输出：6
解释：
子数组 [0] 出现了 4 次。
子数组 [0,0] 出现了 2 次。
不存在长度大于 2 的全 0 子数组，所以我们返回 6 。

示例 2：

输入：nums = [0,0,0,2,0,0]
输出：9
解释：
子数组 [0] 出现了 5 次。
子数组 [0,0] 出现了 3 次。
子数组 [0,0,0] 出现了 1 次。
不存在长度大于 3 的全 0 子数组，所以我们返回 9 。

示例 3：

输入：nums = [2,10,2019]
输出：0
解释：没有全 0 子数组，所以我们返回 0 。

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

写下自己的思路。

数组长度越长，越不能满足题目要求；所以数组长度越短，越能满足条件。

枚举右侧端点，使用不定长滑动窗口算法。为了满足[0,0,2,0,0]这种情况，将last设置成-1,这样的话结果个数就是i-last，因为左侧是开区间，会少一个元素。

三、单序列双指针

3.1 相向双指针

两个指针，$left=0, right=n-1$，从数组的两端开始，向中间移动，这叫做相向双指针。上面的滑动窗口相当于 同向双指针。

344. 反转字符串（20250729）

Details

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]

参考灵神题解：三种写法：双指针/单指针/库函数（Python/Java/C++/C/Go/JS/Rust）

简单来说就是交换对应下标的字符，比如$s[0]$与$s[n-1]$交换，$s[1]$与$s[n-2]$交换，以此类推。

什么时候退出循环？

• 如果n是奇数，最终$left=right=n/2$，无需交换
• 如果n是偶数，最后交换的是$left=n/2-1$，以及$right=n/2$，然后在个移动一位变成$left=n/2，right=n/2-1$，退出循环

所以，当$left>=right$时，所有字符串交换完毕，退出循环。

Java

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
      	// for (int left = 0, right = n - 1; left < right; left++, right--) {
      	// 通过上面的for循环，就可以不单独写left++， right--了
        while (left < right) {
            // 交换两个元素
            char t = s[left];
            s[left] = s[right];
            s[right] = t;
            left++;
            right--;
        }
    }
}

3.2 同向双指针

611. 有效三角形的个数（20250729）

Details

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

判断三条边是否能够组成一个三角形，有两种判定方式，一种是任意两边之和大于第三边，第二种是任意两边之差小于第三边。

借用灵神的题解：两种方法：枚举最长边/枚举最短边（Python/Java/C++/C/Go/JS/Rust）

我们假设三角形的三条边1<a<b<c，那么我们只需要判断 a+b > c， 因为a+c肯定大于b，b+c肯定大于a

Java

class Solution {
    public int triangleNumber(int[] nums) {
        // 枚举最大值
        Arrays.sort(nums);
        int n = nums.length;

        int ans = 0;
        for (int k = 2; k < n; k++) {
            int c = nums[k];
            int i = 0, j = k - 1;
            while (i < j) {
                int a = nums[i], b = nums[j];
                if (a + b > c) {
                    // 为什么是 + (j-1)?
                    // 因为nums[i] + nums[j] > c, nums[i] + nums[j-1] 也是大于c的
                    ans += (j - i);
                    j--;
                } else {
                    i++;
                }
            }
        }
        return ans;

    }
}

141. 环形链表（20250729）

Details

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

经典题目，要使用双指针中快慢指针的技巧，每当慢指针前进一步，快指针前进两步，如果fast最终遇到了空指针，就说明没有环，如果快指针最后和慢指针相遇，那么说明快指针超过了慢指针一圈，说明链表中含有环。

Java

public class Solution {
    public boolean hasCycle(ListNode head) {
        // slow, fast
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

Changelog

8/20/25, 11:06 AM

View All Changelog

• 4c155-Merge branch 'dev1'on 8/20/25