算法母题30道（第1篇）：数组与字符串基础（1-5）

系列说明：本系列共6篇文章，涵盖30道经典算法母题，使用Java实现
适用场景：算法学习、面试准备、编程能力提升

---

30道算法母题总览

第1篇：数组与字符串基础（1-5）⭐ 本篇

1. 两数之和
2. 三数之和
3. 盛最多水的容器
4. 接雨水
5. 最长无重复字符子串

第2篇：链表操作（6-10）

6. 反转链表
7. 合并两个有序链表
8. 链表中倒数第k个节点
9. 判断链表是否有环
10. 合并K个有序链表

第3篇：栈与队列（11-15）

11. 有效的括号
12. 用栈实现队列
13. 最小栈
14. 滑动窗口最大值
15. 每日温度

第4篇：二叉树遍历（16-20）

16. 二叉树的前序遍历
17. 二叉树的中序遍历
18. 二叉树的后序遍历
19. 二叉树的层序遍历
20. 二叉树的最大深度

第5篇：动态规划（21-25）

21. 爬楼梯
22. 最长递增子序列
23. 最长公共子序列
24. 背包问题（0-1背包）
25. 编辑距离

第6篇：搜索与排序（26-30）

26. 二分查找
27. 快速排序
28. 归并排序
29. 岛屿数量（DFS/BFS）
30. 全排列（回溯）

---

第1题：两数之和

📝 题目描述

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

示例：

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

💡 解题思路

1. 暴力法：双重循环遍历所有组合，时间复杂度 O(n²)
2. 哈希表法（推荐）：
   • 遍历数组，对于每个元素 nums[i]
   • 计算需要配对的数：complement = target - nums[i]
   • 检查 complement 是否在哈希表中
   • 如果在，返回当前索引和哈希表中存储的索引
   • 如果不在，将当前元素和索引存入哈希表

🎯 日常应用

• 金融系统：查找两笔交易金额之和等于特定值
• 数据分析：配对数据点满足特定条件
• 推荐系统：找到两个物品的组合满足用户需求
• 游戏开发：匹配玩家等级或分数

🔧 代码解决的问题

• 快速定位满足条件的元素对
• 避免重复计算，提高效率
• 处理大规模数据的查询需求

💻 Java实现代码

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    
    /**
     * 两数之和 - 哈希表法
     * @param nums 输入数组
     * @param target 目标值
     * @return 两个元素的索引数组
     */
    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);
        }
        
        // 题目保证有解，这里不会执行到
        throw new IllegalArgumentException("No two sum solution");
    }
    
    // 测试方法
    public static void main(String[] args) {
        TwoSum solution = new TwoSum();
        
        int[] nums1 = {2, 7, 11, 15};
        int target1 = 9;
        int[] result1 = solution.twoSum(nums1, target1);
        System.out.println("示例1: [" + result1[0] + ", " + result1[1] + "]");
        
        int[] nums2 = {3, 2, 4};
        int target2 = 6;
        int[] result2 = solution.twoSum(nums2, target2);
        System.out.println("示例2: [" + result2[0] + ", " + result2[1] + "]");
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n)

  • 只需要遍历数组一次
  • 哈希表的查找和插入操作平均时间复杂度为 O(1)

• 空间复杂度：O(n)

  • 哈希表最多存储 n 个元素
  • 最坏情况下所有元素都存入哈希表

---

第2题：三数之和

📝 题目描述

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a、b、c，使得 a + b + c = 0。找出所有满足条件且不重复的三元组。

示例：

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

💡 解题思路

1. 排序 + 双指针法：
   • 先对数组排序
   • 固定第一个数 nums[i]
   • 使用双指针 left 和 right 在剩余部分查找
   • 如果三数之和 > 0，right 左移
   • 如果三数之和 < 0，left 右移
   • 如果等于 0，记录结果，同时移动两个指针
2. 去重处理：
   • 跳过重复的 nums[i]
   • 找到解后，跳过重复的 nums[left] 和 nums[right]

🎯 日常应用

• 金融风控：检测三笔异常交易的组合
• 科学计算：求解方程的三个根
• 图像处理：颜色三元组匹配
• 数据聚类：寻找满足特定关系的三个数据点

🔧 代码解决的问题

• 处理多维度的组合问题
• 去重避免重复结果
• 优化暴力搜索的性能

💻 Java实现代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
    
    /**
     * 三数之和 - 排序 + 双指针
     * @param nums 输入数组
     * @return 所有满足条件的三元组
     */
    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++) {
            // 如果当前数字大于0，三数之和不可能为0
            if (nums[i] > 0) {
                break;
            }
            
            // 跳过重复元素
            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;
    }
    
    // 测试方法
    public static void main(String[] args) {
        ThreeSum solution = new ThreeSum();
        
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result = solution.threeSum(nums);
        
        System.out.println("输入: " + Arrays.toString(nums));
        System.out.println("输出: " + result);
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n²)

  • 排序：O(n log n)
  • 外层循环：O(n)
  • 内层双指针：O(n)
  • 总体：O(n log n) + O(n²) = O(n²)

• 空间复杂度：O(1) 或 O(log n)

  • 如果不考虑返回结果的空间
  • 排序可能使用 O(log n) 的栈空间
  • 双指针只使用常数额外空间

---

第3题：盛最多水的容器

📝 题目描述

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

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：选择索引1（高度8）和索引8（高度7），宽度为7，面积 = 7 × 7 = 49

💡 解题思路

双指针法（对撞指针）：

1. 初始化左指针 left = 0，右指针 right = n-1
2. 计算当前容器面积：area = min(height[left], height[right]) × (right - left)
3. 更新最大面积
4. 移动较短的边：
   • 如果 height[left] < height[right]，left++
   • 否则 right–
5. 重复直到 left >= right

为什么移动短边？

• 容器的面积由短板决定
• 移动长边只会让宽度减小，高度不会增加
• 移动短边有可能找到更高的板，增加面积

日常应用

• 建筑设计：计算容器的最大容量
• 物流仓储：优化货物存储空间
• 资源分配：寻找最优的资源配置方案
• 性能优化：带宽或吞吐量的最大化

🔧 代码解决的问题

• 快速找到最优的组合方案
• 避免 O(n²) 的暴力枚举
• 处理一维数组的极值问题

💻 Java实现代码

public class MaxArea {
    
    /**
     * 盛最多水的容器 - 双指针法
     * @param height 高度数组
     * @return 最大面积
     */
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            // 计算当前面积
            int currentHeight = Math.min(height[left], height[right]);
            int currentWidth = right - left;
            int currentArea = currentHeight * currentWidth;
            
            // 更新最大面积
            maxArea = Math.max(maxArea, currentArea);
            
            // 移动较短的边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
    
    // 测试方法
    public static void main(String[] args) {
        MaxArea solution = new MaxArea();
        
        int[] height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        int result = solution.maxArea(height);
        
        System.out.println("输入: " + java.util.Arrays.toString(height));
        System.out.println("最大面积: " + result);
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n)

  • 双指针从两端向中间移动
  • 每个元素最多访问一次

• 空间复杂度：O(1)

  • 只使用了几个变量
  • 不需要额外的存储空间

---

第4题：接雨水

📝 题目描述

给定 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 个单位的雨水

💡 解题思路

动态规划法：

1. 对于每个位置 i，能接的雨水量 = min(左边最高, 右边最高) - height[i]
2. 预处理两个数组：
   • leftMax[i]：位置 i 左边的最高柱子
   • rightMax[i]：位置 i 右边的最高柱子
3. 遍历计算每个位置的雨水量

双指针优化：

• 使用左右指针和左右最大值
• 哪边的最大值小，就处理哪边
• 可以在一次遍历中完成

🎯 日常应用

• 城市规划：计算雨水收集系统的容量
• 农业灌溉：设计蓄水池和灌溉系统
• 土木工程：地形分析和排水设计
• 游戏开发：地形渲染和水体模拟

代码解决的问题

• 计算累积效应（每个位置的贡献）
• 处理边界条件和极值
• 优化空间复杂度的技巧

💻 Java实现代码

public class TrappingRainWater {
    
    /**
     * 接雨水 - 双指针法
     * @param height 高度数组
     * @return 能接的雨水总量
     */
    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;
    }
    
    /**
     * 接雨水 - 动态规划法（更易理解）
     */
    public int trapDP(int[] height) {
        if (height == null || height.length < 3) {
            return 0;
        }
        
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
        
        // 计算左边最大值
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        
        // 计算右边最大值
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
        
        // 计算雨水量
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        
        return water;
    }
    
    // 测试方法
    public static void main(String[] args) {
        TrappingRainWater solution = new TrappingRainWater();
        
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int result = solution.trap(height);
        
        System.out.println("输入: " + java.util.Arrays.toString(height));
        System.out.println("雨水总量: " + result);
    }
}

⏱️ 复杂度分析

双指针法：

• 时间复杂度：O(n) - 一次遍历
• 空间复杂度：O(1) - 只使用常数个变量

动态规划法：

• 时间复杂度：O(n) - 三次遍历
• 空间复杂度：O(n) - 需要两个辅助数组

---

第5题：最长无重复字符子串

📝 题目描述

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

示例：

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

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

解题思路

滑动窗口法：

1. 维护一个滑动窗口 [left, right]
2. 使用哈希表记录字符最后出现的位置
3. 右指针不断向右扩展窗口
4. 如果遇到重复字符：
   • 更新左指针到重复字符的下一个位置
   • 注意：左指针只能向右移动，不能回退
5. 更新最大长度

关键点：

• 左指针的移动公式：left = Math.max(left, map.get(char) + 1)
• 使用 Math.max 确保左指针不会回退

🎯 日常应用

• 文本处理：查找最长唯一子序列
• 数据去重：识别连续的不重复数据段
• 生物信息学：DNA序列分析
• 网络安全：检测异常模式或重复攻击

🔧 代码解决的问题

• 滑动窗口的典型应用
• 处理字符串的子串问题
• 优化暴力枚举的效率

💻 Java实现代码

import java.util.HashMap;
import java.util.Map;

public class LongestSubstringWithoutRepeating {
    
    /**
     * 最长无重复字符子串 - 滑动窗口
     * @param s 输入字符串
     * @return 最长子串的长度
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        // 哈希表记录字符最后出现的位置
        Map<Character, Integer> map = new HashMap<>();
        int maxLength = 0;
        int left = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            
            // 如果字符已存在，更新左指针
            if (map.containsKey(currentChar)) {
                // 左指针只能向右移动，不能回退
                left = Math.max(left, map.get(currentChar) + 1);
            }
            
            // 更新字符位置
            map.put(currentChar, right);
            
            // 更新最大长度
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
    
    // 测试方法
    public static void main(String[] args) {
        LongestSubstringWithoutRepeating solution = new LongestSubstringWithoutRepeating();
        
        String s1 = "abcabcbb";
        System.out.println("输入: \"" + s1 + "\"");
        System.out.println("输出: " + solution.lengthOfLongestSubstring(s1));
        System.out.println();
        
        String s2 = "bbbbb";
        System.out.println("输入: \"" + s2 + "\"");
        System.out.println("输出: " + solution.lengthOfLongestSubstring(s2));
        System.out.println();
        
        String s3 = "pwwkew";
        System.out.println("输入: \"" + s3 + "\"");
        System.out.println("输出: " + solution.lengthOfLongestSubstring(s3));
    }
}

⏱️ 复杂度分析

• 时间复杂度：O(n)

  • 右指针遍历字符串一次
  • 哈希表的查找和插入操作平均 O(1)

• 空间复杂度：O(min(m, n))

  • m 是字符集大小（ASCII 为 128，Unicode 为 65536）
  • n 是字符串长度
  • 哈希表最多存储 min(m, n) 个字符

---

📊 总结与对比

技巧总结

题目	核心技巧	数据结构	时间复杂度	空间复杂度
两数之和	哈希表查找	HashMap	O(n)	O(n)
三数之和	排序 + 双指针	数组	O(n²)	O(1)
盛最多水容器	对撞指针	数组	O(n)	O(1)
接雨水	动态规划/双指针	数组	O(n)	O(1)
最长无重复子串	滑动窗口	HashMap	O(n)	O(min(m,n))

通用解题模板

1. 双指针模板

int left = 0, right = nums.length - 1;
while (left < right) {
    // 处理逻辑
    if (condition) {
        left++;
    } else {
        right--;
    }
}

2. 滑动窗口模板

int left = 0, right = 0;
while (right < nums.length) {
    // 扩大窗口
    // 更新状态
    
    while (需要缩小窗口) {
        // 缩小窗口
        left++;
    }
    
    // 更新结果
    right++;
}

3. 哈希表模板

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    if (map.containsKey(target)) {
        // 找到解
    }
    map.put(nums[i], i);
}

---

📚 下一篇预告

第2篇：链表操作（6-10）

• 反转链表
• 合并两个有序链表
• 链表中倒数第k个节点
• 判断链表是否有环
• 合并K个有序链表

---

如果觉得这篇文章对您有帮助，欢迎：

• 👍 点赞支持
• 💬 留言讨论
• ⭐ 收藏备用

有任何算法问题，欢迎在评论区交流！