获取满足指数的最长字符串

题目

字母表的26个字母，每个字母(忽略大小写)按照他们在字母表的顺序，代表一个数，例如：a代表1，h代表8，z代表26

对于任意由英文字母组成的字符串，我们可以把他们每一位对应的数加起来，便可以计算出这个字符串的指数，例如：abc的指数为6。

现在给你一个字符串与一个期望的指数，希望可以找出这个字符串的所有满足这个指数子串中，最长子串的长度。

要求：时间复杂度为O(n)，空间复杂度为O(1)

输入描述：

输入为两行，第一行是字符串，第二行是期望的指数，例如：

bcdafga
8

输出描述:

输出为最长子串的长度。如果没有合适的子串，则应该返回0，例如，对于示例中的输入，应该输出：
3

解题思路

方法1、双指针：

初始化left和right指针，len指针记录最长子串的长度，res记录当前窗口内数值的和

采用类似滑动窗口的思想

• 当[left,right)窗口内的值等于期望值时，说明找到了一个满足期望的子串，更新最长子串长度，因为此时窗口值已经等于期望值，向右扩展必定会使窗口值增加，所以此时应该缩减左窗口，才有可能在后续的子串中找到另外的满足期望值的left和right，res减去缩减左窗口的值，同时使得left++
• 当[left,right)窗口内的值大于期望值时，需要缩减左窗口，即left++，同时时res减去左窗口的缩减部分的值
• 当[left,right)窗口内的值小于期望值时，需要向右扩展窗口，即right++，同时res加上右窗口增加部分的值

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.nextLine().toCharArray();
        int exNum = Integer.parseInt(sc.nextLine().trim());
        int left = 0;
        int right = 0;
        int len = 0;
        int res = 0;
        while (right < s.length) {
            if (res == exNum) {
                len = Math.max(len, right - left);
                res -= (s[left] - 'a' + 1);
                left++;
            } else if (res > exNum) {
                res -= (s[left] - 'a' + 1);
                left++;
            } else {
                res += (s[right] - 'a' + 1);
                right++;
            }
        }
        System.out.println(len);
    }
}