在这里我总结了一些刷过的leetcode中，常见的关于"子串，子数组“类型的题目，所有题目至少刷了2遍，现在来总结一下经典套路

最长系列

无重复字符的最长子串

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

这道题是leetcode的第三题，需要找出字符串中，不含重读字符的最长子串，在这里，需要对字符串进行遍历，在遍历的过程中，要用一个map存储已扫描到的字符与其下标索引的映射，并且扫描过程中，如果字符没有重复出现的，那么可以用一个变量可以一直更新最长子串的长度

需要注意的是，在扫描过程中时刻要记录最长子串的左右边界，如果扫描到的字符已经出现过了，就要更新左边界，因为要重新开始记录了，但是由于不同字符上一次出现的位置可能不同，为了避免不同而导致字符重复，所以始终要让左边界一直保持最大的情况，才能使得每次更新的子串一定是无重复的

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> m = new HashMap<>();
        int ans = 0;
        int idx = 0;
        for (int i=0;i<s.length();++i) {
            char c = s.charAt(i);
            if (m.containsKey(c)) {
                idx = Math.max(m.get(c) + 1,idx);
            } 
            ans = Math.max(ans,i-idx+1);
            m.put(c,i);
        } 
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最长回文子串

https://leetcode.cn/problems/longest-palindromic-substring/

最长回文子串指的是给一个字符串，正着读和反着读都是一样的，比如"abba"就是一个回文子串，"abbb"则不是，本题可以和以下的 都是一类关于动态规划的问题，可以假设一个场景，如果一个字符串是回文的，那么给这个字符串首尾加上一个相同的字符，这个字符串还是一个回文串，当然单个字符肯定是回文子串，可以使用一个二维数组dp来进行表述，譬如dp[i][j]为1，则代表字符串中下标在[i,j]的子串是一个回文串，如果i等于j，dp[i][j]=1，所以如果字符串下标为i-1的字符和j+1的字符相等，那么dp[i-1][j+1]=1，在这个过程中，我们可以用一个变量随时更新回文子串的最大长度，并且记录子串的左右下标

class Solution {
    public String longestPalindrome(String s) {
        int size = s.length();
        int[][] dp = new int[size][size];
        for (int i=0;i<size;++i) {
            dp[i][i] = 1;
        }
        int ans = 1;
        int left = 0;
        int right = 0;
        for (int i=size-1;i>=0;--i) {
            for (int j=i;j<size;++j) {
                char c1 = s.charAt(i);
                char c2 = s.charAt(j);
                if (c1 == c2) {
                    if (j - i <= 1) {
                        dp[i][j] = 1;
                    } else if (dp[i+1][j-1] == 1) {
                        dp[i][j] = 1;
                    }
                }
                if (dp[i][j] == 1 && j - i + 1 > ans) {
                    ans = j - i + 1;
                    left = i;
                    right = j;
                }
            }
        }
        return s.substring(left,right+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

最长公共子序列

https://leetcode.cn/problems/longest-common-subsequence/

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。最长公共子序列，在本题中表达的是两个字符串中，具有公共的子序列的最大长度，本题和上面的最长回文子串做法相似，都是需要用一个二维的数组来进行状态存储，假设两个不同的字符串，我们用dp[i][j]表示一个状态，表达的是字符串1中[0,i]范围内的子串，字符串2中[0,j]范围内的子串，二者具有相同公共子串的长度，如果此时字符串1下标为i+1的字符等于字符串2中下标为j+1的字符，那么dp[i+1][j+1]=dp[i][j]+1,如果两个字符并不相等，dp[i][j] = max(dp[i-1][j],dp[i][j - 1])，最后状态更新完毕可以获得两个字符串中的最长公共子串

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(),n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i=1;i<=m;++i) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1;j<=n;++j) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    // 如果是公共字符，那就加一个单位长度
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else {
                    // 如果不是公共字符，就
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence/

最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        return maxans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最长连续序列

https://leetcode.cn/problems/longest-consecutive-sequence/

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length < 2) {
            return nums.length;
        }
        Map<Integer,Integer> m = new TreeMap<>();
        for (int i=0;i<nums.length;++i) {
            m.put(nums[i],1);
        }
        int ans = Integer.MIN_VALUE;
        int res = 1;
        int result = 1;
        for (Integer key : m.keySet()) {
            int val = key.intValue();
            if (ans == Integer.MIN_VALUE) {
                ans = key;
            } else {
                if (val - ans == 1) {
                    res++;
                    result = Math.max(res,result);
                } else {
                    res = 1;
                }
                ans = val;
            }
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

最长公共前缀

https://leetcode.cn/problems/longest-common-prefix/

class Solution {
    public String longestCommonPrefix(String[] strs) {
        char[] arr = new char[200];
        Arrays.fill(arr,' ');
        int cur = 200;
        int ans = 200;
        String res = "";
        // 字符串数组只有一个
        if (strs.length == 1) {
            return strs[0];
        }

        // 多个字符串数组
        for (int i=0;i<strs.length;++i) {
            String s = strs[i];
            for (int j=0;j<s.length();++j) {
                if (arr[j]==' ') {
                    arr[j] = s.charAt(j);
                    continue;
                } else if (arr[j] == s.charAt(j)) {
                    cur++;
                } else {
                    break;
                }
            }
            if (cur < ans) {
                ans = cur;
                res = strs[i].substring(0,cur);
            }
            cur = 0;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

最长重复子数组

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m+1][n+1];
        int ans = 0;
        for (int i=1;i<=m;++i) {
            int n1 = nums1[i-1];
            for (int j=1;j<=n;++j) {
                int n2 = nums2[j-1];
                if (n1 == n2) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ans = Math.max(ans,dp[i][j]);
                } 
            }
        }
        return ans;
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

乘积最大的子数组

https://leetcode.cn/problems/maximum-product-subarray/

class Solution {
    public int maxProduct(int[] nums) {
        int len = nums.length;
        int maxarr[] = new int[len];
        int minarr[] = new int[len];
        int max = nums[0];
        maxarr[0] = max;
        minarr[0] = max;
        for(int i=1;i<len;++i){
            //1.nums小于0,NUMS大于0
            maxarr[i] = Math.max(Math.max(maxarr[i-1]*nums[i],minarr[i-1]*nums[i]),nums[i]);
            minarr[i] = Math.min(Math.min(maxarr[i-1]*nums[i],minarr[i-1]*nums[i]),nums[i]);
            max = Math.max(Math.max(maxarr[i],minarr[i]),max);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = 0;
        for (;right<nums.length;++right) {
            sum += nums[right];
            while (sum >= target && right>=left) {
                ans = Math.min(ans,right-left+1);
                sum -= nums[left++];
            }
           
        }
        return ans > nums.length ? 0 : ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

跳跃游戏

https://leetcode.cn/problems/jump-game/

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

雨字系列

接雨水

乘水最多的容器