目录

最大子串和问题(简单)

题目

思路一

思路二

最小子串覆盖问题(困难)

题目

思路一

思路二

最长子串不重复问题(中等)

题目

思路一

思路二

最大子串和问题(简单)

题目

给定一个整数数组，求出数组中连续的最大的子串和。

例如: 2, -1, 3, 5, 6, -3

最大子串和为: 2-1+3+5+6=15

思路一

采用暴力循环的方式，找出每趟最大的子串和，然后再比较每趟的值，最大的那个值即为最大子串和。

完整代码:

   private static Integer findMaxSumStrOne(int[] arr) {        int max = arr[0];        for (int i = 0; i < arr.length; i++) {            int temp = arr[i];            int iMax = temp;            for (int j = i + 1; j < arr.length; j++) {                int current = temp + arr[j];                if (current > iMax) {                    iMax = current;                }                temp = current;            }            if (iMax > max) {                max = iMax;            }        }        return max;    }

此方法虽然能求解，但是时间复杂度为0(n2), 效率比较低。

思路二

采用淘汰的思想,每次只加对当前贡献大的数。

class Solution {   public Integer maxSubArray(int[] arr) {       int ans=arr[0];       int pre=0;       for(int i=0;i<arr.length;i++){           pre=Math.max(arr[i],pre+arr[i]);           ans=Math.max(ans,pre);       }       return ans;    }}

最小子串覆盖问题(困难)题目

给定一个字符串S，字符串T， 求字符串S包含字符串T的最短子串。

例如: S="ADOBECODEBANC", T="ABC"

输出结果: "BANC"

思路一

使用暴力破解的方法

采用顺序字符串的格式获取源字符串的子串，然后用源字符串的子串对目标字符串进行逐个匹配，命中一个字符将目标字符串把该字符给剔除掉，直到目标字符串里的字符全部剔除完毕，就表示找到合适的字符串。

每次找到符合要求的子串(Target)时，比较foundStr和符合要求的Target串的长度，如果长度比源串长度小，就把目标串赋值给foundStr，最终返回结果即可。

也可以根据下标的差值来比较，取差值最小的那个即可。

   private static String findStr(String s, String t) {        if (s.length() < t.length()) {            return "";        }        if (t.length() == 1 && s.contains(t)) {            return t;        }        String foundStr = "";        for (int i = 0; i < s.length(); i++) {            String source = s.charAt(i) + "";            String target = t;            int index = t.indexOf(source);            if (index != -1) {                target = target.substring(0, index) + target.substring(index + 1);                // 目标的子串包含了一个才进行匹配                for (int j = i + 1; j < s.length(); j++) {                    String sub = s.charAt(j) + "";                    // subStr字符串中的所有字符必须全部命中                    int subIndex = target.indexOf(sub);                    if (subIndex != -1) {                        target = target.substring(0, subIndex) + target.substring(subIndex + 1);                        if (target.length() == 0) {                            System.out.println("符合要求:(" + i + "," + j + ")");                            String str = s.substring(i, j + 1);                            if ("".equals(foundStr)) {                                foundStr = str;                            } else {                                foundStr = str.length() <= foundStr.length() ? str : foundStr;                            }                        }                    }                }            }        }        return foundStr;    }

打印结果:

输入: S= "CQDBANC", T="ABC"

输出: BANC

此方法虽然可行，但是时间复杂度是o(n2), 效率比较低,在leetcode里执行会出现超时的情况。

思路二

方法二，采用滑动窗口思想

1) 先将子串的所有字符放到hashMap里，key为字符，value为字符的个数。

2) 然后在主串里设置2个游标，都从左边开始移动，先移动右指针，找到符合条件的子串后，再去移动左指针。

3) j每次找到符合子串的字符（采用map的containsKey()方法来判断），找到符合的count 加1，count初始值为0， 然后hashmap里key对应的value值也-1。同样的i也会向右移动，如果i找到符合的字符在hashmap里，并且hasmap.get(key)==0的情况下，count需要减1，因为map的key对应的value值为0表示j已经找到了符合要求的同样字符，因此count-1。

循环直到count值等于子串的长度值，即找到了覆盖目标子串的字符串。每找到一次与len做比较，取最终长度最小的字符串即可。

滑动窗口思想如下:

此处需要注意的地方:

1) 对于left来讲, 先right++ 然后再判断 , 因为后面的字符我们是不知道的。

2) 对于left来讲，先判断left对应的字符是否满足条件，如果发现left正好命中到了字符串subStr的一个字符，并且right命中过该字符全部的次数(开始时subStr的字符个数)，那么需要count--，然后再left++。

class Solution {    public String minWindow(String s, String t) {        // 用hashmap存放子串字符出现的个数        HashMap<Character, Integer> hashMap = new HashMap<>();        for (int i = 0; i < t.length(); i++) {            if (hashMap.containsKey(t.charAt(i))) {                hashMap.put(t.charAt(i), hashMap.get(t.charAt(i)) + 1);            } else {                hashMap.put(t.charAt(i), 1);            }        }        int left = 0;        int right = -1;        //[left,right] s中包含t字符的出现的次数        int count = 0;        String result = "";        int len = s.length() + 1;        while (left < s.length()) {            if (right + 1 < s.length() && count < t.length()) {                // 滑动右边窗口                right++;                Character rightChar=s.charAt(right);                if (hashMap.containsKey(rightChar)) {                    if (hashMap.get(rightChar) > 0) {                        count++;                    }                    // 如果正好包含右边的字符，那么就将字符出现的次数-1                    hashMap.put(rightChar, hashMap.get(rightChar) - 1);                }            } else {                // count 表示出现t中字符的次数，如果刚好为2，记录满足的结果后，那么就需要移动左指针继续寻找符合条件的最小子串。                // 否则滑动左边窗口                Character leftChar=s.charAt(left);                if (hashMap.containsKey(leftChar)) {                    // 当map中的次数为0时，t中的字符出现的次数-1。                    if (hashMap.get(leftChar) == 0) {                        count--;                    }                    // 每滑动左边窗口，map中的出现的字符+1                    hashMap.put(leftChar, hashMap.get(leftChar) + 1);                }                left++;            }            if (count == t.length()) {                if (right - left + 1 < len) {                    len = right - left + 1;                    result = s.substring(left, right + 1);                }            }        }        return result;    }        }

此算法的时间复杂度为: o(n), 空间复杂度为o(m), m为子串的长度。

最长子串不重复问题(中等)题目

给定一个字符串，找出字符串中最长的不重复的子串，并返回它的长度。

思路一

使用暴力循环破解的方式，通过两次循环，每次取出子串进行判断子串是否是不重复的，然后不断的比较之前的不重复的子串长度，最后返回。

此方式的时间复杂度是大于o(n2), 耗时比较久，不可取。

思路二

滑动窗口思想。

1) 定义左指针和右指针，左指针和右指针之间的窗口为滑动窗口。

2) 右指针每移动一位时，将不重复的字符添加到 Set集合里，Set集合用来判断是否出现重复字符。

3) 当右指针开始遇到重复的字符时，那么计算一次长度，同时左指针右移动一位。

4) 如果左指针移动一位后，右指针的下一位仍然重复，那么在右指针的位置再计算一次长度，同时左指针向右移动一位。

package leetcode100;import java.util.HashSet;import java.util.Set;/** * @decription: * @date: 2021/7/20 17:29 * 给定⼀个字符串，找到没有重复字符的最⻓⼦串，返回它的⻓度。 */public class MaxNotRepeatStrProblem {    public static void main(String[] args) {        String str = "asjfpoajfeskahfiasfjoj";        Integer length = findMaxLengthNotRepeatStr(str);        System.out.println("长度为:" + length);    }    /**     * 实现思路: 每次取出来字符串并判断不重复后，后续判断只需要判断最后一个字符不在之前的字符串里即可，否则滑动窗口。     *  将已有的字符串存在hash里，hash的判断时间复杂度为o(1), 那么总的时间复杂度为o(n)。     * @param str     * @return     */    private static Integer findMaxLengthNotRepeatStr(String s) {        int len=s.length();        int ans=0;        int right=-1;        Set<Character> set=new HashSet<>();        for(int i=0;i<len;i++){             if(i!=0){                set.remove(s.charAt(i-1));            }           while(right+1<len && ! set.contains(s.charAt(right+1))){                set.add(s.charAt(right+1));                   right++;            }            ans=Math.max(ans,right-i+1);        }        return ans;    }}

提交结果: