无重复字符串的最长子串

注意：题目说的是最长子串，而不是最长子序列。

解法一

通过滑动窗口方式解决问题，每一次移动窗口前，记录窗口的长度。并且与前一个窗口比较大小，取最大的记为max。

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();System.out.println(lengthOfLongestSubstring(str));}public static int lengthOfLongestSubstring(String s) {if(s.length() == 0){ //空字符串则直接返回0return 0;}HashSet set = new HashSet<Character>();int left, right = 0; //窗口左右指针int max = 0;//外循环控制左指针移动for(left = 0; left < s.length(); left++){//内循环控制右指针移动while(right < s.length() && !set.contains(s.charAt(right))){set.add(s.charAt(right)); //集合中没有该元素则添加right++;}max = Math.max(max, right - left);set.remove(s.charAt(left)); //移除set集合中做指针指向的元素}return max;}}

解法二

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();System.out.println(lengthOfLongestSubstring(str));}public static int lengthOfLongestSubstring(String s) {if (s.length() == 0) {return 0;}HashMap<Character, Integer> map = new HashMap<>();int left = 0, max = 0;for (int right = 0; right < s.length(); right++) {if (map.containsKey(s.charAt(right))) {left = Math.max(left, map.get(s.charAt(right)) + 1);}map.put(s.charAt(right), right);max = Math.max(max, right - left + 1);}return max;}}

寻找字符串中最长不重复子串、

计算某一段程序消耗的内存和时间

Runtime r = Runtime.getRuntime();
r.gc();//计算内存前先垃圾回收一次long start = System.currentTimeMillis();//开始Time
long startMem = r.freeMemory(); // 开始MemorylengthOfLongestSubstring(str); //被测的程序！！！！！long endMem = r.freeMemory(); // 末尾Memory
long end = System.currentTimeMillis();//末尾TimeSystem.out.println("TimeCost: " + String.valueOf(end - start) + "ms");
System.out.println("MemoryCost: " + String.valueOf((startMem- endMem)/1024) + "MB");