无重复字符的最长子串
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
思路
使用滑动窗口来做，用128数组存储每个窗口中字符所在的位置。
每判断一个新字符，先判断它之前所在的位置+1，与左端所在位置的大小，如果比左端小，就说明新字符再次窗口第一次出现，不需要改变左端。反之则将左端移到比较位置的地方。
+1是因为aba的情况，判断第二个a，左端也是a，要把位置移到b处，所以要有+1的操作
比较结束后，更新ans，然后记录当前元素的位置
Java实现
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] arr = new int[128];
int ans=0;
for(int i=0,j=0;j<s.length();j++){
i=Math.max(i,arr[s.charAt(j)]);
ans=Math.max(ans,j-i+1);
arr[s.charAt(j)]=j+1;
}
return ans;
}
}
执行用时 : 10 ms, 在Longest Substring Without Repeating Characters的Java提交中击败了97.02% 的用户
内存消耗 : 37.4 MB, 在Longest Substring Without Repeating Characters的Java提交中击败了92.81% 的用户
