LeetCode数组与字符串全解析：从基础到高级技巧

安全风信子

发布于 2025-11-13 13:21:07

3760

文章被收录于专栏：AI SPPECHAI SPPECH

一、数组与字符串基础

1.1 数据结构概述

数组和字符串是计算机科学中最基础的数据结构，在LeetCode中也是最常出现的题目类型之一。它们有许多共同的特性，因此经常被放在一起讨论。

数组是一种线性数据结构，它由相同类型的元素组成，并通过索引来访问每个元素。数组的特点是：

元素在内存中连续存储
可以通过索引直接访问任何元素，时间复杂度为O(1)
插入和删除操作效率较低，需要移动元素，时间复杂度为O(n)

字符串本质上是字符数组，在大多数编程语言中，字符串是不可变的（Immutable），这意味着每次修改字符串都会创建一个新的字符串对象。

1.2 常见操作与时间复杂度

操作	数组时间复杂度	字符串时间复杂度
访问	O(1)	O(1)
搜索	O(n)	O(n)
插入	O(n)	O(n) - 由于不可变性
删除	O(n)	O(n) - 由于不可变性
排序	O(n log n)	O(n log n)

1.3 解题常用技巧

双指针法：用于解决数组和字符串的各种问题，如两数之和、反转字符串等
滑动窗口：用于解决子数组和子字符串问题，如最长无重复子串、最小覆盖子串等
二分查找：用于有序数组的查找问题
前缀和：用于快速计算子数组的和
差分数组：用于处理区间更新问题
排序：配合其他算法一起使用，如双指针、贪心等

二、数组经典问题解析

2.1 两数之和（LeetCode 1）

题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

示例：输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0,1]。

解题思路

这道题可以使用哈希表来优化查找过程。

方法一：暴力法

最直接的方法是使用两层循环，枚举所有可能的组合。

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] {i, j};
            }
        }
    }
    return new int[0]; // 没有找到答案
}

时间复杂度：O(n²)，其中n是数组的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

方法二：哈希表法

使用哈希表来存储已经遍历过的元素及其索引，这样可以在O(1)的时间内查找是否存在互补元素。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] {map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[0]; // 没有找到答案
}

时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组。 空间复杂度：O(n)，需要一个哈希表来存储已遍历的元素。

2.2 三数之和（LeetCode 15）

题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

示例：输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

解题思路

这道题可以使用排序+双指针的方法来解决。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length < 3) {
        return result;
    }
    
    // 排序
    Arrays.sort(nums);
    
    for (int i = 0; i < nums.length - 2; i++) {
        // 跳过重复元素
        if (i > 0 && nums[i] == nums[i-1]) {
            continue;
        }
        
        // 双指针
        int left = i + 1;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                // 找到一个解
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                // 跳过重复元素
                while (left < right && nums[left] == nums[left+1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right-1]) {
                    right--;
                }
                
                // 移动指针
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

时间复杂度：O(n²)，其中n是数组的长度。排序的时间复杂度为O(n log n)，双指针遍历的时间复杂度为O(n²)。 空间复杂度：O(log n)，主要是排序所需的空间。

2.3 接雨水（LeetCode 42）

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

解题思路

这道题有多种解法，包括暴力法、动态规划、双指针和单调栈。这里介绍双指针法。

双指针法：

使用两个指针 left 和 right 分别从数组的两端向中间移动
维护两个变量 leftMax 和 rightMax，分别表示左侧和右侧的最大高度
如果 height[left] < height[right]，则 left 向右移动，并计算当前位置能接的雨水量
否则，right 向左移动，并计算当前位置能接的雨水量

public int trap(int[] height) {
    if (height == null || height.length < 3) {
        return 0;
    }
    
    int left = 0;
    int right = height.length - 1;
    int leftMax = 0;
    int rightMax = 0;
    int water = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                water += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                water += rightMax - height[right];
            }
            right--;
        }
    }
    
    return water;
}

时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组。 空间复杂度：O(1)，只使用了常数级别的额外空间。

2.4 盛最多水的容器（LeetCode 11）

题目描述：给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

示例：输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

解题思路

这道题可以使用双指针法来解决。

public int maxArea(int[] height) {
    if (height == null || height.length < 2) {
        return 0;
    }
    
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        // 计算当前的面积
        int currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        
        // 移动指针
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组。 空间复杂度：O(1)，只使用了常数级别的额外空间。

2.5 滑动窗口最大值（LeetCode 239）

题目描述：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

示例：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7]

解题思路

这道题可以使用单调队列（双端队列）来解决。

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k == 0) {
        return new int[0];
    }
    
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new LinkedList<>(); // 存储索引
    
    for (int i = 0; i < n; i++) {
        // 移除队列中超出窗口范围的元素
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        
        // 移除队列中比当前元素小的元素
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        
        // 将当前元素的索引加入队列
        deque.offerLast(i);
        
        // 当窗口形成时，记录最大值
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    
    return result;
}

时间复杂度：O(n)，其中n是数组的长度。每个元素最多入队和出队一次。 空间复杂度：O(k)，队列中最多存储k个元素。

三、字符串经典问题解析

3.1 最长无重复字符的子串（LeetCode 3）

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

示例：输入：s = “abcabcbb” 输出：3 解释：因为无重复字符的最长子串是 “abc”，所以其长度为 3。

解题思路

这道题可以使用滑动窗口结合哈希集合来解决。

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.isEmpty()) {
        return 0;
    }
    
    Set<Character> set = new HashSet<>();
    int left = 0;
    int maxLength = 0;
    
    for (int right = 0; right < s.length(); right++) {
        // 如果字符已经存在于集合中，移动左指针直到字符被移除
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        
        // 将当前字符加入集合
        set.add(s.charAt(right));
        
        // 更新最大长度
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

时间复杂度：O(n)，其中n是字符串的长度。每个字符最多被访问两次。 空间复杂度：O(min(n, m))，其中m是字符集的大小。在最坏情况下，需要存储整个字符集的字符。

3.2 有效的括号（LeetCode 20）

题目描述：给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例：输入：s = “()” 输出：true

解题思路

这道题可以使用栈来解决。

public boolean isValid(String s) {
    if (s == null || s.isEmpty()) {
        return true;
    }
    
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            // 左括号入栈
            stack.push(c);
        } else {
            // 右括号
            if (stack.isEmpty()) {
                return false;
            }
            
            char top = stack.pop();
            if ((c == ')' && top != '(') || 
                (c == '}' && top != '{') || 
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    
    // 栈为空表示所有括号都匹配
    return stack.isEmpty();
}

时间复杂度：O(n)，其中n是字符串的长度。需要遍历一次字符串。 空间复杂度：O(n)，在最坏情况下，需要将所有的字符都入栈。

3.3 最长回文子串（LeetCode 5）

题目描述：给你一个字符串 s，找到 s 中最长的回文子串。

示例：输入：s = “babad” 输出：“bab” 或 “aba”

解题思路

这道题有多种解法，包括中心扩展法和动态规划。这里介绍中心扩展法。

中心扩展法：

回文串都是关于中心对称的，可以枚举所有可能的中心位置
中心位置可能是一个字符（奇数长度的回文串）或两个相邻字符之间的位置（偶数长度的回文串）
从中心位置向两边扩展，直到不再是回文串

public String longestPalindrome(String s) {
    if (s == null || s.isEmpty()) {
        return "";
    }
    
    int start = 0;
    int end = 0;
    
    for (int i = 0; i < s.length(); i++) {
        // 奇数长度的回文串，中心是一个字符
        int len1 = expandAroundCenter(s, i, i);
        // 偶数长度的回文串，中心是两个字符之间的位置
        int len2 = expandAroundCenter(s, i, i + 1);
        
        int maxLen = Math.max(len1, len2);
        if (maxLen > end - start) {
            start = i - (maxLen - 1) / 2;
            end = i + maxLen / 2;
        }
    }
    
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    // 返回回文串的长度
    return right - left - 1;
}

时间复杂度：O(n²)，其中n是字符串的长度。需要枚举所有可能的中心位置，并从中心向两边扩展。 空间复杂度：O(1)，只使用了常数级别的额外空间。

3.4 最小覆盖子串（LeetCode 76）

题目描述：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

示例：输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”

解题思路

这道题可以使用滑动窗口结合哈希表来解决。

public String minWindow(String s, String t) {
    if (s == null || t == null || s.isEmpty() || t.isEmpty()) {
        return "";
    }
    
    // 统计t中每个字符的出现次数
    Map<Character, Integer> target = new HashMap<>();
    for (char c : t.toCharArray()) {
        target.put(c, target.getOrDefault(c, 0) + 1);
    }
    
    // 滑动窗口
    Map<Character, Integer> window = new HashMap<>();
    int left = 0;
    int right = 0;
    int valid = 0; // 已经包含的t中字符的数量
    int start = 0;
    int minLen = Integer.MAX_VALUE;
    
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        
        // 更新窗口
        if (target.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(target.get(c))) {
                valid++;
            }
        }
        
        // 窗口已经包含了t中的所有字符，尝试缩小窗口
        while (valid == target.size()) {
            // 更新最小子串
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }
            
            char d = s.charAt(left);
            left++;
            
            // 更新窗口
            if (target.containsKey(d)) {
                if (window.get(d).equals(target.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

时间复杂度：O(n)，其中n是字符串s的长度。滑动窗口的左右指针最多各移动n次。 空间复杂度：O(k)，其中k是字符集的大小。在最坏情况下，需要存储整个字符集的字符。

3.5 字符串的排列（LeetCode 567）

题目描述：给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

示例：输入：s1 = “ab” s2 = “eidbaooo” 输出：true 解释：s2 包含 s1 的排列之一 (“ba”)。

解题思路

这道题可以使用滑动窗口结合哈希表来解决。

public boolean checkInclusion(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() > s2.length()) {
        return false;
    }
    
    // 统计s1中每个字符的出现次数
    int[] target = new int[26];
    for (char c : s1.toCharArray()) {
        target[c - 'a']++;
    }
    
    // 滑动窗口
    int[] window = new int[26];
    int left = 0;
    int right = 0;
    
    while (right < s2.length()) {
        char c = s2.charAt(right);
        window[c - 'a']++;
        right++;
        
        // 当窗口大小超过s1的长度时，移动左指针
        while (right - left > s1.length()) {
            char d = s2.charAt(left);
            window[d - 'a']--;
            left++;
        }
        
        // 检查窗口中的字符是否与s1的字符匹配
        if (right - left == s1.length() && isMatch(window, target)) {
            return true;
        }
    }
    
    return false;
}

private boolean isMatch(int[] window, int[] target) {
    for (int i = 0; i < 26; i++) {
        if (window[i] != target[i]) {
            return false;
        }
    }
    return true;
}

时间复杂度：O(n)，其中n是字符串s2的长度。滑动窗口的左右指针最多各移动n次。 空间复杂度：O(1)，使用了固定大小的数组。

四、数组与字符串进阶问题

4.1 寻找两个正序数组的中位数（LeetCode 4）

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

示例：输入：nums1 = [1,3], nums2 = [2] 输出：2.0 解释：合并数组 = [1,2,3] ，中位数是 2

解题思路

这道题可以使用二分查找来解决。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    
    // 确保nums1是较短的数组
    if (m > n) {
        return findMedianSortedArrays(nums2, nums1);
    }
    
    int total = m + n;
    int left = 0;
    int right = m;
    
    while (left <= right) {
        int i = left + (right - left) / 2;
        int j = (total + 1) / 2 - i;
        
        // 计算四个边界值
        int maxLeft1 = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int minRight1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int maxLeft2 = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int minRight2 = (j == n) ? Integer.MAX_VALUE : nums2[j];
        
        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            // 找到正确的分割点
            if (total % 2 == 0) {
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            // 需要向左移动分割点
            right = i - 1;
        } else {
            // 需要向右移动分割点
            left = i + 1;
        }
    }
    
    throw new IllegalArgumentException("Input arrays are not sorted");
}

时间复杂度：O(log(min(m, n)))，其中m和n分别是两个数组的长度。使用二分查找的时间复杂度为O(log(min(m, n)))。 空间复杂度：O(1)，只使用了常数级别的额外空间。

4.2 最长公共子序列（LeetCode 1143）

题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

示例：输入：text1 = “abcde”, text2 = “ace” 输出：3 解释：最长公共子序列是 “ace”，它的长度为 3。

解题思路

这道题可以使用动态规划来解决。

public int longestCommonSubsequence(String text1, String text2) {
    if (text1 == null || text2 == null || text1.isEmpty() || text2.isEmpty()) {
        return 0;
    }
    
    int m = text1.length();
    int n = text2.length();
    
    // dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度
    int[][] dp = new int[m + 1][n + 1];
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[m][n];
}

时间复杂度：O(mn)，其中m和n分别是两个字符串的长度。需要填充m×n的dp数组。 空间复杂度：O(mn)，需要一个m×n的dp数组。

4.3 编辑距离（LeetCode 72）

题目描述：给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例：输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)

解题思路

这道题可以使用动态规划来解决。

public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return 0;
    }
    
    int m = word1.length();
    int n = word2.length();
    
    // dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作数
    int[][] dp = new int[m + 1][n + 1];
    
    // 初始化边界条件
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 取插入、删除、替换三种操作的最小值
                dp[i][j] = Math.min(
                    Math.min(dp[i - 1][j], dp[i][j - 1]), // 删除和插入
                    dp[i - 1][j - 1]                     // 替换
                ) + 1;
            }
        }
    }
    
    return dp[m][n];
}

时间复杂度：O(mn)，其中m和n分别是两个字符串的长度。需要填充m×n的dp数组。 空间复杂度：O(mn)，需要一个m×n的dp数组。

4.4 寻找重复数（LeetCode 287）

题目描述：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例：输入：nums = [1,3,4,2,2] 输出：2

解题思路

这道题可以使用快慢指针法（Floyd的龟兔算法）来解决，类似于环形链表的检测。

public int findDuplicate(int[] nums) {
    if (nums == null || nums.length < 2) {
        throw new IllegalArgumentException("Input array is invalid");
    }
    
    // 快慢指针
    int slow = nums[0];
    int fast = nums[nums[0]];
    
    // 找到相遇点
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    
    // 找到环的入口点（重复的数）
    slow = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    
    return slow;
}

时间复杂度：O(n)，其中n是数组的长度。 空间复杂度：O(1)，只使用了常数级别的额外空间。

4.5 缺失的第一个正数（LeetCode 41）

题目描述：给你一个未排序的整数数组 nums，请你找出其中没有出现的最小的正整数。

示例：输入：nums = [1,2,0] 输出：3

解题思路

这道题可以使用原地哈希的思想来解决。

public int firstMissingPositive(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 1;
    }
    
    int n = nums.length;
    
    // 步骤1：将负数和0替换为n+1
    for (int i = 0; i < n; i++) {
        if (nums[i] <= 0) {
            nums[i] = n + 1;
        }
    }
    
    // 步骤2：标记存在的数
    for (int i = 0; i < n; i++) {
        int num = Math.abs(nums[i]);
        if (num <= n) {
            nums[num - 1] = -Math.abs(nums[num - 1]);
        }
    }
    
    // 步骤3：找出第一个正数的位置
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }
    
    return n + 1;
}

时间复杂度：O(n)，其中n是数组的长度。需要遍历数组三次。 空间复杂度：O(1)，只使用了常数级别的额外空间。

五、数组与字符串实战技巧总结

5.1 常用数据结构

哈希表/集合：用于快速查找、去重、统计频率等操作
栈：用于处理括号匹配、表达式求值等问题
队列/双端队列：用于滑动窗口、广度优先搜索等问题
堆：用于优先级队列、堆排序等问题

5.2 常见算法思想

双指针：同向双指针、相向双指针、快慢指针等
滑动窗口：固定窗口大小、可变窗口大小
二分查找：适用于有序数组的查找问题
动态规划：解决最优子结构问题
贪心算法：局部最优解得到全局最优解
递归/回溯：解决组合、排列等问题

5.3 优化技巧

空间换时间：使用哈希表等数据结构来提高查找效率
原地操作：尽量在原数组上进行操作，减少额外空间的使用
预处理：对数据进行排序、统计等预处理，以便后续操作
剪枝：在递归/回溯过程中，提前排除不可能的情况

5.4 注意事项

边界条件：处理空数组、单元素数组等特殊情况
数据范围：注意整数溢出等问题
时间限制：根据题目要求选择合适的算法，避免超时
空间限制：在空间有限的情况下，考虑原地算法

六、面试高频数组与字符串问题

6.1 最大子数组和（LeetCode 53）

题目描述：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例：输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

解题思路

这道题可以使用动态规划或贪心算法来解决。这里介绍动态规划法。

public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        // 当前和 = max(当前元素，当前和+当前元素)
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        // 更新最大和
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组。 空间复杂度：O(1)，只使用了常数级别的额外空间。

6.2 合并区间（LeetCode 56）

题目描述：以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例：输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6].

解题思路

这道题可以使用排序+贪心的方法来解决。

public int[][] merge(int[][] intervals) {
    if (intervals == null || intervals.length <= 1) {
        return intervals;
    }
    
    // 按照区间的起始位置排序
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0]);
    
    for (int i = 1; i < intervals.length; i++) {
        int[] lastMerged = merged.get(merged.size() - 1);
        int[] current = intervals[i];
        
        if (current[0] <= lastMerged[1]) {
            // 区间重叠，合并
            lastMerged[1] = Math.max(lastMerged[1], current[1]);
        } else {
            // 区间不重叠，添加新的区间
            merged.add(current);
        }
    }
    
    return merged.toArray(new int[merged.size()][]);
}

时间复杂度：O(n log n)，其中n是区间的数量。排序的时间复杂度为O(n log n)。 空间复杂度：O(log n)，主要是排序所需的空间。

6.3 字母异位词分组（LeetCode 49）

题目描述：给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

示例：输入：strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出：[[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

解题思路

这道题可以使用哈希表来解决。

public List<List<String>> groupAnagrams(String[] strs) {
    if (strs == null || strs.length == 0) {
        return new ArrayList<>();
    }
    
    Map<String, List<String>> map = new HashMap<>();
    
    for (String str : strs) {
        // 将字符串转换为字符数组并排序
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        
        // 将原字符串添加到对应的列表中
        if (!map.containsKey(key)) {
            map.put(key, new ArrayList<>());
        }
        map.get(key).add(str);
    }
    
    return new ArrayList<>(map.values());
}

时间复杂度：O(nk log k)，其中n是字符串数组的长度，k是字符串的最大长度。对每个字符串进行排序的时间复杂度为O(k log k)。 空间复杂度：O(nk)，需要存储所有的字符串。

七、数组与字符串思维训练与扩展

7.1 多维数组的处理

多维数组是一维数组的扩展，常见的有二维数组和三维数组。在处理多维数组时，需要注意以下几点：

索引访问：多维数组的索引是从外到内的
边界条件：注意每个维度的边界条件
遍历方式：可以按行遍历、按列遍历或对角线遍历等

7.2 字符串匹配算法

字符串匹配是字符串处理中的一个重要问题，常见的算法有：

暴力匹配：时间复杂度为O(mn)
KMP算法：时间复杂度为O(m+n)
Boyer-Moore算法：在实际应用中通常比KMP更快
Rabin-Karp算法：使用哈希函数进行匹配

7.3 数组与字符串在实际应用中的体现

数据库索引：使用B+树等数据结构，其底层实现依赖于数组
文本处理：字符串的搜索、替换、分割等操作
图像处理：图像可以表示为二维数组，每个元素代表一个像素
网络协议：数据包的解析和组装

八、总结与展望

数组和字符串是算法面试中最基础也是最重要的题型，掌握好这两类题型的解法，对于解决其他更复杂的算法问题至关重要。

通过本文的学习，我们了解了数组和字符串的基本概念、常见操作和时间复杂度，掌握了双指针、滑动窗口、二分查找、动态规划等常用算法思想，并通过具体的LeetCode题目解析，深入理解了这些算法思想的实际应用。

在解决数组和字符串问题时，我们需要注意以下几点：

理解问题：仔细阅读题目，明确输入输出要求和约束条件
选择合适的算法：根据问题的特点选择合适的算法思想
优化时间和空间复杂度：在保证正确性的前提下，尽量优化算法的时间和空间复杂度
处理边界条件：考虑空数组、单元素数组等特殊情况
测试验证：通过示例和边界情况验证算法的正确性

通过不断地练习和总结，我们可以提高解决数组和字符串问题的能力，为更复杂的算法学习打下坚实的基础。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串