滑动窗口

无重复字符的最长子串长度

经典面试题，用滑动窗口 + HashSet实现。

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // 有重复，移动左指针，直到移除重复字符
            while (set.contains(c)) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(c);
            // 更新最大长度
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
        System.out.println(lengthOfLongestSubstring("bbbbb"));    // 1
        System.out.println(lengthOfLongestSubstring("pwwkew"));   // 3
    }
}

题目到底在说什么？

题目：给定一个字符串 s，找出【不包含重复字符】的【最长子串】的长度。

拆解成 3 个关键词你就懂了：

  1. 子串：必须是连续的一段字符（不能跳着选）
  2. 无重复字符：里面每个字符只能出现一次
  3. 最长：在所有符合条件的子串里，找长度最大的那个

最终答案：返回这个最大长度（不是返回子串本身）

超级通俗例子 1

输入：abcabcbb

我们一步步看所有连续、无重复的子串：

  • 从 a 开始：

    • a ✅ 长度 1
    • ab ✅ 长度 2
    • abc ✅ 长度 3
    • abca ❌ a 重复了

  • 从 b 开始：

    • b → bc → bca → bcab ❌ b 重复

  • 从 c 开始：

    • c → ca → cab → cabc ❌ c 重复

  • …… 后面所有无重复子串，最长都只有 3

✅ 答案：3

对应子串就是：abc、bca、cab 这些长度都是 3。

例子 2：最简单的情况

输入：bbbbb

所有子串：

  • b ✅
  • bb ❌ 重复
  • bbb ❌ 重复
  • ...

所有无重复子串最长只能是 1

✅ 答案：1

例子 3：最容易错的情况（必看）

输入：pwwkew

我们一步步找：

  1. p ✅
  2. pw ✅
  3. pww ❌ w 重复 → 从下一个 w 重新开始
  4. w ✅
  5. wk ✅
  6. wke ✅ （长度 3）
  7. wkew ❌ w 重复

最长无重复子串是：wke 或 kew

✅ 答案：3

再给你一个极端例子

输入：abcdefg

整个字符串完全没有重复

所以最长子串就是它自己！

✅ 答案：7

4. 给定一个链表，判断是否有环

判断链表是否有环（Java 经典面试题）

这道题最优解法是快慢指针法（龟兔赛跑算法），时间复杂度 O(n)，空间复杂度 O(1)，面试手写首选。

  1. 算法：快慢指针（最优解）
  2. 时间：O(n)，只需遍历一次链表
  3. 空间：O(1)，只用两个指针，无额外空间
  4. 结论：相遇=有环，快指针到末尾=无环

核心思路

  1. 定义两个指针：慢指针（slow） 每次走1步，快指针（fast） 每次走2步
  2. 如果链表有环：快指针一定会在环内追上慢指针（相遇）
  3. 如果链表无环：快指针会先走到链表末尾（null）

完整 Java 代码

// 链表节点定义
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class HasCycle {
    // 判断链表是否有环
    public boolean hasCycle(ListNode head) {
        // 空链表 或 只有一个节点，肯定无环
        if (head == null || head.next == null) {
            return false;
        }

        // 快慢指针初始化
        ListNode slow = head;
        ListNode fast = head;

        // 快指针不能走到null
        while (fast != null && fast.next != null) {
            slow = slow.next;          // 慢指针走1步
            fast = fast.next.next;     // 快指针走2步

            // 快慢指针相遇 = 有环
            if (slow == fast) {
                return true;
            }
        }

        // 快指针走到末尾 = 无环
        return false;
    }

    // 测试用例
    public static void main(String[] args) {
        HasCycle solution = new HasCycle();

        // 测试1：有环链表
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(3);
        head1.next.next.next = head1.next; // 3 指向 2，形成环
        System.out.println(solution.hasCycle(head1)); // true

        // 测试2：无环链表
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        System.out.println(solution.hasCycle(head2)); // false
    }
}

代码关键点

  1. 边界判断：链表为空/只有一个节点，直接返回 false
  2. 循环条件：fast != null && fast.next != null，防止快指针空指针异常
  3. 相遇即有环：只要快慢指针相遇，就说明链表存在环

总结

  1. 双栈队列：一个入队、一个出队，空时倒数据
  2. 反转链表：迭代改指针，空间 O(1)
  3. 最长无重复子串：滑动窗口 + 哈希集合，时间 O(n)
  4. 链表判断是否有环：快慢指针，时间O(n)，空间 O(1)