3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
substring要想到滑动窗口，不过这道题是求最大的窗口而已，每步都要更新max
tricky的地方在于start只能向右移动，比如abba碰见最后的a，start会移动index=1的地方，就错了。
public int lengthOfLongestSubstring(String s) {
// key is char value its index
Map<Character, Integer> map = new HashMap<>();
int max = 0, start = 0;
for (int i = 0; i < s.length(); i++) {
if (map.containsKey(s.charAt(i))) {
// find duplicate, update start
// start can only move to right
if (start < map.get(s.charAt(i)) + 1) {
start = map.get(s.charAt(i)) + 1;
}
}
max = Math.max(max, i - start + 1);
map.put(s.charAt(i), i);
}
return max;
}
先找到满足条件的，记录，尝试缩小窗口
while循环三步走，先update最值，删开头尝试新可能性，最后挪start
209. Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
1+3+1+3=8>7，所以让8减第一个元素尝试去缩小window，更新最小值，然后减第二个直到不能缩小，指针停下。
while循环三步走，先update最值，删开头尝试新可能性，最后挪start
public int minSubArrayLen(int s, int[] nums) {
int sum = 0, start = 0, res = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
while (sum >= s) {
res = Math.min(res, (i - start + 1));
sum -= nums[start];
start++;
}
}
return (res == Integer.MAX_VALUE) ? 0 : res;
}
76. Minimum Window Substring
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
思路和上题一样，找最小的窗口
Sliding Window
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
for (char c : t.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int start = 0, minSize = Integer.MAX_VALUE, minStart = 0, count = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if (map.get(c) >= 0) {
count++;
}
}
// A -1, B 0， 存在负数的可能
while (count == t.length()) {
// update
if (i - start + 1 < minSize) {
minSize = i - start + 1;
minStart = start;
}
// delete first
char r = s.charAt(start);
if (map.containsKey(r)) {
map.put(r, map.get(r) + 1);
// 注意是 > 0, 过剩了再减 ex. AAB
if (map.get(r) > 0) {
count--;
}
}
start++;
}
}
return (minSize == Integer.MAX_VALUE) ? "" : s.substring(minStart, minStart + minSize);
}
}
438. Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
一开始对anagram的定义有些误解。要明白start指针移动的过程。套路和上题一样
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
Map<Character, Integer> map = new HashMap<>();
for (char c : p.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int start = 0;
int count = 0;
for (int end = 0; end < s.length(); end++) {
char cur = s.charAt(end);
if (map.containsKey(cur)) {
map.put(cur, map.get(cur) - 1);
if (map.get(cur) >= 0) {
count++;
}
}
while (count == p.length()) {
char c = s.charAt(start);
if(map.containsKey(c)) {
map.put(c, map.get(c) + 1);
if (map.get(c) > 0) {
count--;
}
}
if (end - start + 1 == p.length()) {
res.add(start);
}
start++;
}
}
return res;
}
