11.盛最多水的容器

Posted on 2025-11-26 Edited on 2026-03-26 In leetcode , 面试经典150题

双指针

容器的面积由两部分决定，一部分是两条线之间的宽度，另一部分是两条线中较短的那一条，因为水位只能由短板决定。

因此可以让两个指针分别指向数组两端，先计算当前容器面积。之后为了尝试得到更大的答案，应当移动较短的那一侧。因为如果移动较高的一侧，宽度一定变小，而短板仍然可能还是原来那根较短的线，这样面积不可能变得更大；只有移动短板，才有机会找到更高的边，从而弥补宽度缩小带来的损失。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int ans = 0;
        while (left < right) {
            int high = Math.min(height[left], height[right]);
            ans = Math.max(ans, (right - left) * high);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
}

167.两数之和II-输入有序数组

Posted on 2025-11-25 Edited on 2026-03-26 In leetcode , 面试经典150题

双指针

数组已经按非递减顺序排列，这个有序性质正好可以利用起来。

设左指针 $left$ 指向最小值，右指针 $right$ 指向最大值。若两数之和小于 $target$，说明当前和偏小，需要让左指针右移来增大和；若两数之和大于 $target$，说明当前和偏大，需要让右指针左移来减小和。这样每次都能排除一部分不可能的情况。

由于题目保证恰好存在一个答案，因此当两数之和等于 $target$ 时，直接返回对应下标即可。注意题目下标从 $1$ 开始，所以最终答案需要加一。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                break;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{left + 1, right + 1};
    }
}

392.判断子序列

Posted on 2025-11-24 Edited on 2026-03-26 In leetcode , 面试经典150题

双指针

判断子序列的关键在于，s 中的字符只需要按顺序出现在 t 中即可，不要求连续。

因此可以用两个指针，i 指向 s，j 指向 t。固定 i，不断向右移动 j，直到在 t 中找到和 s[i] 相同的字符。如果一直找到 t 末尾都没找到，说明 s 不是 t 的子序列；否则继续匹配 s 的下一个字符。

如果最终 s 的所有字符都能依次找到，那么它就是 t 的子序列。

时间复杂度 $O(m + n)$

空间复杂度 $O(1)$

class Solution {
    public boolean isSubsequence(String s, String t) {
        int m = s.length();
        int n = t.length();
        int j = 0;
        for (int i = 0; i < m; ++i) {
            while (j < n && t.charAt(j) != s.charAt(i)) {
                j++;
            }
            if (j == n) {
                return false;
            }
            j++;
        }
        return true;
    }
}

125.验证回文串

Posted on 2025-11-23 Edited on 2026-03-26 In leetcode , 面试经典150题

双指针

题目要求忽略非字母数字字符，并且字母忽略大小写，因此可以使用双指针分别从字符串两端向中间扫描。

如果当前字符不是字母或数字，就直接跳过；当左右两侧都停在有效字符后，再判断它们是否相同。数字必须完全相同，字母则只需忽略大小写后相同即可。只要有一组字符不匹配，就不是回文串。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0;
        int right = n - 1;
        while (left < right) {
            while (left < right && !isLetter(s.charAt(left)) && !isNumber(s.charAt(left))) {
                left++;
            }
            while (left < right && !isLetter(s.charAt(right)) && !isNumber(s.charAt(right))) {
                right--;
            }
            if (left >= right) {
                break;
            }
            if (!isSameChar(s.charAt(left), s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    private boolean isLetter(char c) {
        if (c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z') {
            return true;
        }
        return false;
    }

    private boolean isNumber(char c) {
        if (c >= '0' && c <= '9') {
            return true;
        }
        return false;
    }

    private boolean isSameChar(char c1, char c2) {
        if (isNumber(c1) && isNumber(c2)) {
            return c1 == c2;
        }
        if (isLetter(c1) && isLetter(c2) && (c1 - c2 == 0 || c1 - c2 == 'a' - 'A' || c1 - c2 == 'A' - 'a')) {
            return true;
        }
        return false;
    }
}

双指针

也可以直接调用语言自带的字符判断函数，使写法更简洁。

同样用左右指针从两端向中间移动，先跳过所有非字母数字字符，再把当前位置字符统一转成小写后比较。这样就把“过滤无效字符”和“忽略大小写”都统一处理掉了。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0;
        int right = n - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

28.找出字符串中第一个匹配项的下标

Posted on 2025-11-22 Edited on 2026-03-26 In leetcode , 面试经典150题

模拟

最直接的做法就是枚举主串中每一个可能作为起点的位置，然后判断从这里开始能否完整匹配 needle。

如果当前位置开始的每个字符都和 needle 对应位置相同，那么就返回这个起点下标；否则继续尝试下一个位置即可。

时间复杂度 $O(nm)$

空间复杂度 $O(1)$

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack.length() < needle.length()) {
            return -1;
        }
        for (int i = 0; i < haystack.length() - needle.length() + 1; ++i) {
            if (check(haystack, i, needle)) {
                return i;
            }
        }
        return -1;
    }

    private boolean check(String haystack, int start, String needle) {
        if (haystack.length() - start + 1 < needle.length()) {
            return false;
        }
        for (int i = 0; i < needle.length(); ++i) {
            if (haystack.charAt(start + i) != needle.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

KMP

朴素匹配在失配时会回退主串指针，很多比较其实是重复的。KMP 的核心就在于，失配后不回退主串，而是利用模式串自身的信息，直接把模式串滑到一个合适位置继续匹配。

具体来说，先为模式串预处理出 next 数组，表示当某个位置失配时，模式串指针下一步应跳到哪里。这样在匹配过程中，一旦字符不同，就可以快速跳过不可能匹配的部分，从而把总时间复杂度优化到 $O(n + m)$。

时间复杂度 $O(n + m)$

空间复杂度 $O(m)$

class Solution {
    public int strStr(String haystack, String needle) {
        return kmp(haystack, needle);
    }
    
    private int kmp(String target, String pattern) {  // 时间复杂度：O(n + m)
        int n = target.length();      // 主串长度
        int m = pattern.length();     // 模式串长度

        // 边界情况处理
        if (m == 0) {                 // 空模式串
            return 0;
        }
        if (n < m) {                  // 主串比模式串短，不可能匹配
            return -1;
        }
        
        // 1. 计算模式串的next数组（部分匹配表）
        int[] next = getNext(pattern);
        
        // 2. 进行KMP匹配
        int i = 0;  // 主串指针
        int j = 0;  // 模式串指针
        
        while (i < n && j < m) {
            // 情况1：模式串第一个字符就匹配失败（j=-1），或者当前字符匹配成功
            if (j == -1 || target.charAt(i) == pattern.charAt(j)) {
                i++;  // 主串指针后移
                j++;  // 模式串指针后移
            } 
            // 情况2：字符不匹配，根据next数组跳转模式串指针
            else {
                j = next[j];  // 模式串指针回退到next[j]位置
            }
        }
        
        // 匹配结果判断
        if (j == m) {          // 模式串完全匹配成功
            return i - j;      // 返回匹配的起始索引
        } else {               // 匹配失败
            return -1;
        }
    }
    
    private int[] getNext(String pattern) {  // 时间复杂度：O(m)
        int n = pattern.length();      // 模式串长度
        int[] next = new int[n];       // 创建next数组
        next[0] = -1;                  // 初始值，表示模式串第一个字符匹配失败时需要特殊处理
        
        int i = 0;  // 后缀末尾指针
        int j = -1; // 前缀末尾指针（初始为-1，表示无前缀）
        
        // 构建next数组，注意循环条件是 i < n-1
        while (i < n - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;  // 模式串指针后移
                j++;  // 已匹配的前缀长度增加
                next[i] = j;
            } else {// j 回退，但回退次数小于等于前进次数即i增加量（if分支中二者同步增加i意味着j增加了多少次）
                j = next[j];  // 利用已计算的next值进行回退
            }
        }
        return next;
    }
}

6.Z字形变换

Posted on 2025-11-21 Edited on 2026-03-26 In leetcode , 面试经典150题

按行访问

观察 $Z$ 字形排列可以发现，字符的分布具有周期性。

当行数为 $numRows$ 时，一个完整周期长度为 $2 \times numRows - 2$。对于第 $row$ 行而言，每个周期中一定会出现一个位置 $i + row$ 的字符；如果这一行既不是第一行也不是最后一行，那么同一周期内还会额外出现一个斜着走的位置 $i + cycle - row$。

因此可以直接按行枚举，每一行把属于它的字符按顺序加入答案即可。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        StringBuilder ans = new StringBuilder();
        int n = s.length();
        int cycle = 2 * numRows - 2;
        for (int row = 0; row < numRows; ++row) {
            for (int i = 0; i + row < n; i += cycle) {
                ans.append(s.charAt(i + row));
                if (row != 0 && row != numRows - 1 && i + cycle - row < n) {
                    ans.append(s.charAt(i + cycle - row));
                }
            }
        }
        return ans.toString();
    }
}

模拟走位

也可以直接模拟字符在各行之间来回移动的过程。

准备 $numRows$ 个字符串，依次把字符放入当前行中。当走到第一行或最后一行时，就改变移动方向，于是在各行之间上下折返。最终再把所有行拼接起来，就是按题目要求逐行读取后的结果。

这种写法更符合题意描述，按实际书写过程完成模拟。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        List<StringBuilder> rows = new ArrayList<StringBuilder>();
        for (int i = 0; i < numRows; ++i) {
            rows.add(new StringBuilder());
        }
        int i = 0, flag = -1;
        for (char c : s.toCharArray()) {
            rows.get(i).append(c);
            if (i == 0 || i == numRows - 1) flag = -flag;
            i += flag;
        }
        StringBuilder ans = new StringBuilder();
        for (StringBuilder row : rows) {
            ans.append(row);
        }
        return ans.toString();
    }
}

151.反转字符串中的单词

Posted on 2025-11-20 Edited on 2026-03-26 In leetcode , 面试经典150题

倒序遍历

题目要求反转单词顺序，同时去掉多余空格，因此可以直接从后往前遍历字符串，每次提取一个完整单词加入答案。

做法是从字符串末尾开始，先跳过空格，再找到当前单词的左右边界，将该单词加入结果。之后继续向前重复这一过程。由于是按从后往前提取，所以最终拼接出的字符串天然就是单词逆序，同时只在单词之间手动加一个空格即可避免多余空格。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = new StringBuilder();
        int end = s.length() - 1;
        for (;;) {
            int[] cur = getWord(s, end);
            end = cur[0] - 1;
            if (cur[0] == -1) {
                break;
            }
            sb.append(s, cur[0], cur[1]);
            sb.append(' ');
        }
        if (sb.length() > 0) {
            sb.setLength(sb.length() - 1);
        }
        return sb.toString();
    }

    private int[] getWord(String s, int i) {
        int[] ans = new int[]{-1, -1};
        while (i >= 0 && s.charAt(i) == ' ') {
            i--;
        }
        if (i >= 0) {
            ans[1] = i + 1;
            while (i >= 0 && s.charAt(i) != ' ') {
                i--;
            }
            ans[0] = i + 1;
        }
        return ans;
    }
}

双指针

也可以先去掉首尾空格，然后用双指针在字符串中从右往左扫描。

设 $r$ 和 $l$ 都指向当前待处理单词的末尾，先让 $l$ 左移找到这个单词的起点，再把这一段加入答案。随后继续跳过前面的空格，并更新下一轮单词的右边界。这样同样能够按逆序提取所有单词。

这种写法更紧凑，本质上仍然是从后往前逐个找单词。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        int r = s.length() - 1, l = r;
        StringBuilder ans = new StringBuilder();
        while (l >= 0) {
            while (l >= 0 && s.charAt(l) != ' ') {
                l--;
            }
            ans.append(s, l + 1, r + 1).append(' ');
            while (l >= 0 && s.charAt(l) == ' ') {
                l--;
            }
            r = l;
        }
        return ans.toString().trim();
    }
}

14.最长公共前缀

Posted on 2025-11-19 Edited on 2026-03-26 In leetcode , 面试经典150题

纵向扫描

最长公共前缀的含义，就是所有字符串在前若干个位置上的字符都相同，因此可以按列来检查。

先求出所有字符串中的最短长度，因为公共前缀长度不可能超过它。随后从第 $0$ 列开始依次判断，取第一个字符串当前位置的字符作为基准，再和其余字符串同一位置的字符比较。如果某一列出现不同字符，说明公共前缀到此为止；否则就把该字符加入答案。

时间复杂度 $O(nm)$

空间复杂度 $O(1)$

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int minLen = Integer.MAX_VALUE;
        for (String s : strs) {
            minLen = Math.min(minLen, s.length());
        }
        int n = strs.length;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < minLen; ++i) {
            char cur = strs[0].charAt(i);
            boolean flag = true;
            for (int j = 1; j < n; ++j) {
                if (strs[j].charAt(i) != cur) {
                    flag = false;
                }
            }
            if (!flag) {
                break;
            }
            sb.append(cur);
        }
        return sb.toString();
    }
}

以第一个字符串为基准

也可以直接把第一个字符串当作候选答案。

遍历第一个字符串的每一个位置，检查其余所有字符串在该位置是否也存在且字符相同。只要某个字符串已经到头，或者当前位置字符不同，就说明公共前缀只能到当前位置之前，直接返回第一个字符串的前缀即可。

这种写法本质上也是纵向扫描，只是省去了额外统计最短长度的过程。

时间复杂度 $O(nm)$

空间复杂度 $O(1)$

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        String first = strs[0];
        for (int i = 0; i < first.length(); ++i) {
            char cur = first.charAt(i);
            for (String s : strs) {
                if (i == s.length() || s.charAt(i) != cur) {
                    return first.substring(0, i);
                }
            }
        }
        return first;
    }
}

58.最后一个单词的长度

Posted on 2025-11-18 Edited on 2026-03-26 In leetcode , 面试经典150题

倒序遍历

最后一个单词前面可能有若干单词，后面也可能有空格，因此直接从前往后找不如从后往前找更直接。

先从字符串末尾开始跳过所有空格，找到最后一个单词的结尾位置；再继续向左遍历，直到遇到空格或到达字符串开头，此时这段区间的长度就是最后一个单词的长度。

时间复杂度 $O(n)$

空间复杂度 $O(1)$

class Solution {
    public int lengthOfLastWord(String s) {
        int i = s.length() - 1;
        while (s.charAt(i) == ' ') {
            i--;
        }
        int last = i;
        while (i >= 0 && s.charAt(i) != ' ') {
            i--;
        }
        return last - i;
    }
}

12.整数转罗马数字

Posted on 2025-11-17 Edited on 2026-03-26 In leetcode , 面试经典150题

贪心

罗马数字的构造规则本质上就是每次优先使用当前能表示的最大数值符号，因此可以直接按照从大到小的顺序不断选取。

例如遇到 $1994$ 时，先取 $1000$ 对应的 $M$，剩余 $994$；再取 $900$ 对应的 $CM$，剩余 $94$；再取 $90$ 对应的 $XC$，最后取 $4$ 对应的 $IV$。这样依次拼接即可得到答案。

由于题目中所有可能用到的数值组合都是固定的，因此只需要把这些值按从大到小列出来，遍历时不断减去并拼接对应符号即可。

时间复杂度 $O(1)$

空间复杂度 $O(1)$

class Solution {
    private static final Map<Integer, String> map = new TreeMap<>(Collections.reverseOrder());
    static {
        map.put(1000, "M");
        map.put(900, "CM");
        map.put(500, "D");
        map.put(400, "CD");
        map.put(100, "C");
        map.put(90, "XC");
        map.put(50, "L");
        map.put(40, "XL");
        map.put(10, "X");
        map.put(9, "IX");
        map.put(5, "V");
        map.put(4, "IV");
        map.put(1, "I");
    }
    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            int value = entry.getKey();
            String symbol = entry.getValue();

            while (num >= value) {
                sb.append(symbol);
                num -= value;
            }
        }
        return sb.toString();
    }
}

数组模拟

上面的写法思路很直接，不过这里其实并不需要真的使用 Map，因为所有数值和符号都是固定顺序的，直接用两个数组一一对应即可。

遍历 values 数组时，如果当前数值还能从 num 中减去，就把对应的罗马字符加入答案，并继续减去，直到不能再减为止。由于可选项只有固定的 $13$ 个，所以整体仍然是常数时间。

时间复杂度 $O(1)$

空间复杂度 $O(1)$

class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < values.length; ++i) {
            int value = values[i];
            String symbol = symbols[i];

            while (num >= value) {
                sb.append(symbol);
                num -= value;
            }
        }
        return sb.toString();
    }
}