? LeetCode 热题 HOT 100 : 03 && 04

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

3. 无重复字符的最长子串

一、题目描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

二、思路分析：

• 滑动窗口 + 哈希表， 哈希表记录 字符对应的位置 index, 遍历过程中 遇到当前字符在哈希表中出现时，意味当前滑动窗口中存在了重复的字符， 因此需要更新左端点为 max(当前字符上次出现的位置 + 1, 当前左端点的位置)， 遍历过程中实时更新滑动窗口的 size

三、AC 代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();

        char[] chars = s.toCharArray();
        int ans = 0;
        for(int j = 0, i = 0; j < chars.length; j++){
            if(map.containsKey(chars[j])){
                i = Math.max(i, map.get(chars[j]) + 1);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(chars[j], j);
        }

        return ans;

    }
}
复制代码

4. 寻找两个正序数组的中位数

一、题目描述：

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,2], nums2 = [3,4]

输出：2.50000

解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

二、思路分析：

二分， 求第 k 小的数字， 每次从两个数组中取 k / 2 个数字， 比较最后一位数字的大小， 数字较小的那块区域无法作为候选，可以删掉， 继续递归求解第 k/2 小的数字， 递归中止的条件是 k == 1，直接比较即可

三、AC 代码：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int sum = nums1.length + nums2.length;
        if((sum & 1) == 1){
            return getKNum(nums1, 0, nums2, 0, sum / 2 + 1);
        }else{
            int l = getKNum(nums1, 0, nums2, 0, sum / 2);
            int r = getKNum(nums1, 0, nums2, 0, sum / 2  + 1);
            return (l + r) / 2.0;
        }
    }

    int getKNum(int[] nums1, int i, int[] nums2, int j, int k){
        if(nums1.length - i> nums2.length - j ) return getKNum(nums2, j, nums1, i, k);

        if(i >= nums1.length) return nums2[j + k - 1];
        if(k == 1) return Math.min(nums1[i], nums2[j]);

        int a = Math.min(i + k/2, nums1.length);
        int b = j + k - k/2;

        if(nums1[a - 1] >= nums2[b - 1]){
            return getKNum(nums1, i, nums2, b, k - (b - j));
        }else{
            return getKNum(nums1, a, nums2, j, k - (a - i));
        }
    }
}
复制代码