滑动窗口

class SlideWindow {
public static void main(String[] a) {
int[] arr = {100, 200, 300, 400};
int k = 2;
int maxSum = maxSum(arr, k);

    System.out.println(maxSum);

    String S = "ADOBECODEBANC";

    String T = "ABC";

    String findedSubStr = findShortestSubStringContainTStr(S, T);

    System.out.println(findedSubStr);


}

private static String findShortestSubStringContainTStr(String s, String t) {
    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();
    int sLen = sChars.length;

    int left = 0;
    int right = 0;
    int start = 0;
    int end = 0;
    int minWidth = Integer.MAX_VALUE;
    int tempWidth = 0;

    right = left + 1;
    String subStr;

    while (right <= sLen) {

        subStr = s.substring(left, right);
        //如果窗口不包含目标子串的所有字母，则向右扩宽窗口
        if (contrainsAll(subStr, t)) {
            //如果窗口内已包含目标子串的所有字母，则记录此时的start,end位置
            tempWidth = right - left;
            if (tempWidth < minWidth) {
                minWidth = tempWidth;
                start = left;
                end = right;
            }

            //尝试从左侧缩小窗口
            //从左侧缩小一位
            left = left + 1;
            while (left < right) {
                subStr = s.substring(left, right);

                if (contrainsAll(subStr, t)) {
                    //更新起始位置
                    tempWidth = right - left;
                    if (tempWidth < minWidth) {
                        minWidth = tempWidth;
                        start = left;
                        end = right;
                    }
                    left++;
                } else {
                    break;
                }
            }
        }
        right++;
    }
    return s.substring(start, end);
}

private static boolean contrainsAll(String s, String t) {
    char[] tChars = t.toCharArray();
    for (int i = 0; i < tChars.length; i++) {
        String temp = String.valueOf(tChars[i]);
        if (!s.contains(temp)) {
            return false;
        }
    }
    return true;
}

private static int maxSum(int[] arr, int k) {
    int len = arr.length;
    int max = 0;
    for (int i = 0; i < k; i++) {
        max += arr[i];
    }

    for (int j = 0; j < len - k; j++) {
        int temp = max - arr[j] + arr[j + k];
        max = max > temp ? max : temp;
    }

    return max;
}

}