双指针

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

移除元素

快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
慢指针：指向更新新数组下标的位置

当快指针与移除的目标值相等时，将快指针向前移动一位，慢指针保持不变，此时慢指针指向的就是需要被替换的数组下标位置

当快指针与移除的目标值不相等时，因为此时慢指针指向的是需要被替换的数组下标位置，所以将快指针的值赋给慢指针，完成覆盖，最后再将慢指针移动一位

public int removeElement(int[] nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

删除有序数组中的重复项

比较 left 和 right 位置的元素是否相等

如果相等，right 后移 1 位
如果不相等，将 right 位置的元素复制到 left +1 位置上，left 后移一位，right 后移 1 位
重复上述过程，直到 right 等于数组长度

返回 left + 1，即为新数组长度

public int removeDuplicates(int[] nums) {
    int left = 0;
    int right = 1;
    while (right < nums.length){
        if (nums[left] != nums[right]){
            left++;
            nums[left] = nums[right];
        }
        right++;
    }
    return left + 1;
}

移动零

当右指针为0时，说明该数字需要交换，所以将右指针移动一位，左指针不变

当右指针不为0时，将左右指针所指向的元素进行交换，之后让左右指针都移动一位

public void moveZeroes(int[] nums) {
    int left = 0;
    int right = 0;
    while (right < nums.length){
        if (nums[right] != 0){
            swap(nums,left++,right);
        }
        right++;
    }
}

有序数组的平方

从两端遍历，找到平方最大元素放到数组末尾，判断左指针平方后的值和右指针平方后的值哪个大，选择大的哪一个放到数组的最末尾end处，然后把end往前移动一位，如果左指针平方后的值大，就将左指针向右移动一位，反之则将右指针向左移动一位

public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    
    for (int left = 0, right = n - 1, end = n - 1; left <= right; ) {
        if (nums[left] * nums[left] > nums[right] * nums[right]) {
            res[end--] = nums[left] * nums[left++];
        } else {
            res[end--] = nums[right] * nums[right--];
        }
    }
    return res;
}

x 的平方根

参考该题解：二分查找（Java） - x 的平方根 - 力扣（LeetCode）

如果目标数小于x的算术平方根，这个数可能是我们要找的那个数

如果目标数大于x的算术平方根，这个数不可能是我们要找的那个数

如果目标数等于x的算术平方根，这个数即为我们要找的数

所以可以用二分查找来查找这个目标数，不断缩小范围

将猜的数定为mid，因为x的算术平方根一定比 2 / x 小，所以将右边界定为x / 2，左边界定为0

当mid > x / mid（为了防止溢出），此时目标数只可能存在区间 [left，mid - 1]

当mid < x / mid（为了防止溢出），此时目标数只可能存在区间 [mid，right]

public int mySqrt(int x) {
    if (x == 0) return 0;
    if (x == 1) return 1;
    int left = 0;
    int right = x / 2;
    //在 [left,right] 查找目标元素
    while (left < right) {
        int mid = left + (right - left +  1) / 2;
        if (mid > x / mid) {
            // 搜索区间变为 [left,mid - 1]
            right = mid - 1;
        }else {
            // 搜索区间变为 [mid,right]
            left = mid;
        }
    }
    return left;
}

第一个错误的版本

当一个版本为正确版本，则该版本之前的所有版本都是正确版本；当一个版本为错误版本，则该版本之后的所有版本都是错误版本

left指向第一个版本，right为指向最后一个版本，每次都判断中间的版本是否错误，如果错误说明边界为[left，mid+1]，如果正确则说明边界为[mid，right]

public int firstBadVersion(int n) {
    if (n == 1) return 1;
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        }else {
            left = mid + 1;
        }
    }
    return left;
}

猜数字大小

public int guessNumber(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (guess(mid) == 0) {
            return mid;
        } else if (guess(mid) == 1) {
            left = mid + 1;
        } else if (guess(mid) == -1) {
            right = mid;
        }
    }
    return left;
}

旋转数组的最小数字

当 nums[m]>nums[j] 时： m一定在左排序数组中，即旋转点x一定在[m+1，j]闭区间内，因此执行i = m + 1；

当 nums[m]<nums[j] 时： m一定在右排序数组中，即旋转点x一定在[i，m]闭区间内，因此执行 j = m；

当 nums[m]=nums[j] 时： 无法判断m在哪个排序数组中，即无法判断旋转点x在[i，m] 还是[m+1，j]区间中此时对right–缩小判断范围，由于它们的值相同，所以无论numbers[right]是不是最小值，都有一个它的替代
numbers[pivot]，因此可以忽略二分查找区间的右端点

1、为什么right–不会对结果产生影响？
产生影响条件：删除的元素为唯一最小元素
与执行条件：numbers[right]==numbers[mid]矛盾

2、为什么right=mid，而left=mid+1

public int minArray(int[] numbers) {
    int left = 0;
    int right = numbers.length - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (numbers[mid] > numbers[right]) {
            left = mid + 1;
        }else if (numbers[mid] < numbers[right]) {
            right = mid;
        }else if (numbers[mid] == numbers[right]) {
            right--;
        }
    }
    return numbers[left];
}

滑动窗口

长度最小的子数组

该题中滑动窗口中的元素就是 sum ≥ s 的长度最小的连续数组

如果当前滑动窗口内的值（sum）小于s，那么就让滑动窗口的右边界往前移动，并让sum加上移动后的元素

如果当前滑动窗口内的值（sum）大于s，那么该滑动窗口就要向前移动了，在向前移动后，sum要减去当前滑动窗口的左边界的值，并让左边界向右移动一位

还需要一个变量result来记录在遍历过程中长度最小的数组的长度，在每次sum>s的时候进行记录

最后判断result是否为默认的初始值，如果是，则说明在遍历过程中不存在符合条件的子数组，返回0即可

public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }

https://hzzzzzy-typora.oss-cn-guangzhou.aliyuncs.com/images/202210142213737.png

https://hzzzzzy-typora.oss-cn-guangzhou.aliyuncs.com/images/202210142213356.png

子数组最大平均数 I

滑动窗口长度为k

sum表示当前滑动窗口内元素的和

max表示滑动窗口内元素最大的和

1、首先创建出第一个滑动窗口，并计算出sum，并将max初始化为sum

2、然后将滑动窗口向右移动，在移动后，计算sum的大小，并对比sum和max的大小，取出较大值赋给max

3、最后返回max / k并强转为double

（double计算比int要慢，所以中间记录的值要设成int型，最后返回的时候再转换成double）

public double findMaxAverage(int[] nums, int k) {
    int sum = 0;
    int max;
    for (int i = 0; i < k; i++) {
        sum += nums[i];
    }
    max = sum;
    for (int i = k; i < nums.length; i++) {
        sum = sum - nums[i - k] + nums[i];
        max = Math.max(max,sum);
    }
    return (double) max / k;
}

最长的美好子字符串

待解决

长度为三且各字符不同的子字符串

滑动窗口的长度为3

res记录符合条件的子字符串

首先定义i指向滑动窗口的右边界，然后判断滑动窗口内是否有重复字符（即让 i 与 i-1 , i-2 互相比较）

如果都没有相等的字符，则符合条件，让res++，之后让滑动窗口一直向右移动，对每个滑动窗口内都进行重复字符的判断

public int countGoodSubstrings(String s) {
    char[] chars = s.toCharArray();
    int res = 0;
    for (int i = 2; i < s.length(); i++) {
        if (chars[i] != chars[i - 1] && chars[i] != chars[i - 2] && chars[i - 1] != chars[i - 2]) {
            res++;
        }
    }
    return res;
}

得到 K 个黑块的最少涂色次数

该题可以理解为求出连续黑色块中最少出现的白色块，滑动窗口的长度为k

1、先将字符串处理为字符数组，然后遍历数组k次，遇到’W’字符时就加一

2、之后对数组后面的元素进行遍历，每次滑动窗口向前移动一位，并通过temp记录移动后出现的白色块

（滑动窗口的左边界如果是’W’字符，则让temp–，滑动窗口的右边界如果是’W’字符，则让temp++）

3、最后将滑动窗口移动前后中出现的白色块temp和min，进行比较，取较小值

public int minimumRecolors(String blocks, int k) {
    char[] chars = blocks.toCharArray();
    int min;
    int temp = 0;
    for (int i = 0; i < k; i++) {
        if (chars[i] == 'W') {
            temp++;
        }
    }
    min = temp;
    for(int i = k;i < blocks.length();i++){
        if(chars[i-k]=='W'){
            temp--;
        }
        if(chars[i]=='W'){
            temp++;
        }
        min = Math.min(min,temp);
    }
    return min;
}

无重复字符的最长子串

该题可以先划定一个滑动窗口，然后右边界先向右开始移动，直到不符合条件为止（通过map的containsKey方法来进行判断）

当不符合条件时左边界开始收缩，直到符合条件为止，然后继续让右边界开始移动重复上面的操作

public int lengthOfLongestSubstring(String s) {
    if (s.length() == 0) return 0;
    HashMap<Character, Integer> map = new HashMap<>();
    char[] chars = s.toCharArray();
    int left = 0;
    int res = 0;
    for (int right = 0; right < chars.length; right++) {
        // 如果元素在map中已经存在
        if (map.containsKey(chars[right])) {
            left = Math.max(left,map.get(chars[right]) + 1);
        }
        map.put(chars[right],right);
        res = Math.max(res, right - left + 1);
    }
    return res;
}

至少有 K 个重复字符的最长子串

public int longestSubstring(String s, int k) {
    int res = 0;
    for (int kind = 0; kind <= 26; kind++) {
        int left = 0;   //左边界
        int right = 0;  //右边界
        int[] windows = new int[26];  //用来记录窗口内字符出现的次数
        int type = 0;  //窗口内字符的种类
        int conform_type = 0;   //窗口内符合目标条件的字符种类
        while (right < s.length()) {
            int temp = s.charAt(right) - 'a';
            //进入滑动窗口
            windows[temp]++;
            if (windows[temp] == 1){    //第一次进入
                type++;
            }
            if (windows[temp] == k){    //符合条件
                conform_type++;
            }
            //窗口向右移动
            while (type > kind) {
                int leftChar = s.charAt(left) - 'a';
                if (windows[leftChar] == 1) {
                    type--;
                }
                if (windows[leftChar] == k) {
                    conform_type--;
                }
                windows[leftChar]--;
                left++;
            }
            // 取符合要求的子串的最大长度
            if (conform_type == type) {
                res = Math.max(res, right - left + 1);
            }
            right++;
        }
    }
    return res;
}

替换后的最长重复字符

public int characterReplacement(String s, int k) {
        char[] chars = s.toCharArray();
        if (chars.length < 2) {
            return chars.length;
        }
        int left = 0;
        int right = 0;
        int res = 0;
        int max = 0;
        int[] temp = new int[26];
        while (right < chars.length) {
            //右边界向右移动
            temp[chars[right] - 'A']++;
            max = Math.max(max, temp[chars[right] - 'A']);
            if (right - left > max + k) {
                //左边界向右移动
                temp[chars[left++] - 'A']--;
            }
            res = Math.max(res, right - left);
        }
        return res;
    }

KMP算法

解决在一个串（文本串）中查找是否出现过

另一个串（模式串）的问题

理论

1、前缀：包含首字母，不包含尾字母的所有字串

假如一个字符串为“aabcaa”那么前缀有“a”“aa”“aab”“aabc”“aabca”

2、后缀：只包含尾字母，不包含首字母的所有字串

假如一个字符串为“aabcaa”那么后缀有“a”“aa”“aac”“aacb”“aabca”

3、最长相等（公共）前后缀长度

字符串“a”：0

字符串“aa”：1

字符串“aab”：0

字符串“aabc”：0

字符串“aabca”：1

字符串“aabcaa”：2

4、前缀表

如字符串“aabcaa”前缀表为：010012

5、使用前缀表的匹配过程

假设有一个文本串为“aabaabaaf”模式串为“aabaaf”

文本串“aabaabaaf”的前缀表为：0 1 0 1 2 0

在匹配过程中，当模式串第一次出现与文本串不匹配时，模式串中不匹配元素的前一个位置和首字母构成了一个字串，在该子串的前缀表中（01012）找到最大的公共前缀为2

然后以最大公共前缀为下标处继续开始匹配，该模式串中下标为2，所以从b处继续匹配

6、next数组

里面存放前缀表或者对前缀表进行一些具体的操作，来完成匹配失败后，跳转到之前匹配的位置的操作