top3
解法一
简单粗暴些，找一个最长子串，那么我们用两个循环穷举所有子串，然后再用一个函数判断该子串中有没有重复的字符。
publicintlengthOfLongestSubstring(Strings) { intn=s.length(); intans=0;//保存当前得到满足条件的子串的最大值for (inti=0; i<n; i++) for (intj=i+1; j<=n; j++) //之所以 j<= n，是因为我们子串是 [i,j),左闭右开if (allUnique(s, i, j)) ans=Math.max(ans, j-i); //更新 ansreturnans; } publicbooleanallUnique(Strings, intstart, intend) { Set<Character>set=newHashSet<>();//初始化 hash setfor (inti=start; i<end; i++) {//遍历每个字符Characterch=s.charAt(i); if (set.contains(ch)) returnfalse; //判断字符在不在 set 中set.add(ch);//不在的话将该字符添加到 set 里边 } returntrue; }
时间复杂度：两个循环，加上判断子串满足不满足条件的函数中的循环，O（n³）。
空间复杂度：使用了一个 set，判断子串中有没有重复的字符。由于 set 中没有重复的字符，所以最长就是整个字符集，假设字符集的大小为 m ，那么 set 最长就是 m 。另一方面，如果字符串的长度小于 m ，是 n 。那么 set 最长也就是 n 了。综上，空间复杂度为 O（min（m，n））。
解法二
遗憾的是上边的算法没有通过 leetCode，时间复杂度太大，造成了超时。我们怎么来优化一下呢？
上边的算法中，我们假设当 i 取 0 的时候，
j 取 1，判断字符串 str[0,1) 中有没有重复的字符。
j 取 2，判断字符串 str[0,2) 中有没有重复的字符。
j 取 3，判断字符串 str[0,3) 中有没有重复的字符。
j 取 4，判断字符串 str[0,4) 中有没有重复的字符。
做了很多重复的工作，因为如果 str[0,3) 中没有重复的字符，我们不需要再判断整个字符串 str[0,4) 中有没有重复的字符，而只需要判断 str[3] 在不在 str[0,3) 中，不在的话，就表明 str[0,4) 中没有重复的字符。
如果在的话，那么 str[0,5) ，str[0,6) ，str[0,7) 一定有重复的字符，所以此时后边的 j 也不需要继续增加了。i ++ 进入下次的循环就可以了。
此外，我们的 j 也不需要取 j + 1，而只需要从当前的 j 开始就可以了。
综上，其实整个关于 j 的循环我们完全可以去掉了，此时可以理解变成了一个「滑动窗口」。
整体就是橘色窗口在依次向右移动。
判断一个字符在不在字符串中，我们需要可以遍历整个字符串，遍历需要的时间复杂度就是 O（n），加上最外层的 i 的循环，总体复杂度就是 O（n²）。我们可以继续优化，判断字符在不在一个字符串，我们可以将已有的字符串存到 Hash 里，这样的时间复杂度是 O（1），总的时间复杂度就变成了 O（n）。
publicclassSolution { publicintlengthOfLongestSubstring(Strings) { intn=s.length(); Set<Character>set=newHashSet<>(); intans=0, i=0, j=0; while (i<n&&j<n) { if (!set.contains(s.charAt(j))){ set.add(s.charAt(j++)); ans=Math.max(ans, j-i); } else { set.remove(s.charAt(i++)); } } returnans; } }
时间复杂度：在最坏的情况下，while 循环中的语句会执行 2n 次，例如 abcdefgg，开始的时候 j 一直后移直到到达第二个 g 的时候固定不变 ，然后 i 开始一直后移直到 n ，所以总共执行了 2n 次，时间复杂度为 O（n）。
空间复杂度：和上边的类似，需要一个 Hash 保存子串，所以是 O（min（m，n））。
top4
已知两个有序数组，找到两个数组合并后的中位数。
解法一
简单粗暴，先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数。
publicdoublefindMedianSortedArrays(int[] nums1, int[] nums2) { int[] nums; intm=nums1.length; intn=nums2.length; nums=newint[m+n]; if (m==0) { if (n%2==0) { return (nums2[n/2-1] +nums2[n/2]) /2.0; } else { returnnums2[n/2]; } } if (n==0) { if (m%2==0) { return (nums1[m/2-1] +nums1[m/2]) /2.0; } else { returnnums1[m/2]; } } intcount=0; inti=0, j=0; while (count!= (m+n)) { if (i==m) { while (j!=n) { nums[count++] =nums2[j++]; } break; } if (j==n) { while (i!=m) { nums[count++] =nums1[i++]; } break; } if (nums1[i] <nums2[j]) { nums[count++] =nums1[i++]; } else { nums[count++] =nums2[j++]; } } if (count%2==0) { return (nums[count/2-1] +nums[count/2]) /2.0; } else { returnnums[count/2]; } }
时间复杂度：遍历全部数组，O（m + n）
空间复杂度：开辟了一个数组，保存合并后的两个数组，O（m + n）
解法二
其实，我们不需要将两个数组真的合并，我们只需要找到中位数在哪里就可以了。
开始的思路是写一个循环，然后里边判断是否到了中位数的位置，到了就返回结果，但这里对偶数和奇数的分类会很麻烦。当其中一个数组遍历完后，出了 for 循环对边界的判断也会分几种情况。总体来说，虽然复杂度不影响，但代码会看起来很乱。然后在 这里 找到了另一种思路。
首先是怎么将奇数和偶数的情况合并一下。
用 len 表示合并后数组的长度，如果是奇数，我们需要知道第 （len + 1）/ 2 个数就可以了，如果遍历的话需要遍历 int ( len / 2 ) + 1 次。如果是偶数，我们需要知道第 len / 2 和 len / 2 + 1 个数，也是需要遍历 len / 2 + 1 次。所以遍历的话，奇数和偶数都是 len / 2 + 1 次。
返回中位数的话，奇数需要最后一次遍历的结果就可以了，偶数需要最后一次和上一次遍历的结果。所以我们用两个变量 left 和 right ，right 保存当前循环的结果，在每次循环前将 right 的值赋给 left 。这样在最后一次循环的时候，left 将得到 right 的值，也就是上一次循环的结果，接下来 right 更新为最后一次的结果。
循环中该怎么写，什么时候 A 数组后移，什么时候 B 数组后移。用 aStart 和 bStart 分别表示当前指向 A 数组和 B 数组的位置。如果 aStart 还没有到最后并且此时 A 位置的数字小于 B 位置的数组，那么就可以后移了。也就是aStart ＜ m && A[aStart] < B[bStart]。
但如果 B 数组此刻已经没有数字了，继续取数字B [ bStart ]，则会越界，所以判断下 bStart 是否大于数组长度了，这样 || 后边的就不会执行了，也就不会导致错误了，所以增加为 aStart ＜ m && ( bStart >= n || A [ aStart ] < B [ bStart ] ) 。
publicdoublefindMedianSortedArrays(int[] A, int[] B) { intm=A.length; intn=B.length; intlen=m+n; intleft=-1, right=-1; intaStart=0, bStart=0; for (inti=0; i<=len/2; i++) { left=right; if (aStart<m&& (bStart>=n||A[aStart] <B[bStart])) { right=A[aStart++]; } else { right=B[bStart++]; } } if ((len&1) ==0) return (left+right) /2.0; elsereturnright; }
时间复杂度：遍历 len/2 + 1 次，len = m + n ，所以时间复杂度依旧是 O（m + n）。
空间复杂度：我们申请了常数个变量，也就是 m，n，len，left，right，aStart，bStart 以及 i 。
总共 8 个变量，所以空间复杂度是 O（1）。
