第1天：数组与字符串算法实战（Java 实现）

1. 典型问题分析

问题1：两数之和（Two Sum）

题目描述

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

示例

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

2. 解决方案（多种方式）

方法1：暴力枚举（O(n²))

思路：

• 使用两层 for 循环遍历数组的所有可能的数对，检查它们的和是否等于 target。

public int[] twoSumBruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{}; // 没有找到返回空数组
}

缺点：时间复杂度 O(n²)，适用于小规模数据。

方法2：哈希表优化（O(n)）

思路：

• 使用 HashMap 存储遍历过的数字和它们的索引。
• 遍历数组时，计算 target - nums[i] 是否已在 HashMap 中，如果存在，则直接返回两个索引。

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

public int[] twoSumHashMap(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[]{};
}

优点：

• 通过 HashMap 进行 O(1) 查询，时间复杂度 O(n)，适用于大规模数据。
• 空间复杂度为 O(n)，因为 HashMap 需要额外存储元素。

问题2：最长无重复子串（Longest Substring Without Repeating Characters）

题目描述

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

示例

输入: s = "abcabcbb"
输出: 3
解释: 最长不重复子串是 "abc"，长度为3。

2. 解决方案（多种方式）

方法1：暴力枚举（O(n²))

思路：

• 逐个遍历子串，检查是否有重复字符，更新最长长度。

public int lengthOfLongestSubstringBruteForce(String s) {
    int maxLength = 0;
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            if (hasDuplicate(s, i, j)) break;
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

private boolean hasDuplicate(String s, int start, int end) {
    Set<Character> set = new HashSet<>();
    for (int i = start; i <= end; i++) {
        if (set.contains(s.charAt(i))) return true;
        set.add(s.charAt(i));
    }
    return false;
}

缺点：时间复杂度 O(n²)，适用于小规模字符串。

方法2：滑动窗口（O(n)）

思路：

• 使用 双指针（left, right） 和 HashSet 记录窗口内字符。
• 移动右指针 扩展窗口，如果出现重复字符，则 移动左指针 缩小窗口，直到没有重复字符。

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

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int maxLength = 0, left = 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)，比暴力解法更高效。
• 适用于 大规模字符串处理。

问题3：最大子数组和（Kadane’s Algorithm）

题目描述

给定一个整数数组 nums，找到 连续子数组（最少包含一个元素），使其和最大，并返回最大和。

示例

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

2. 解决方案

方法1：暴力枚举（O(n²))

思路：

• 计算所有可能的子数组和，找出最大值。

public int maxSubArrayBruteForce(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            maxSum = Math.max(maxSum, sum);
        }
    }
    return maxSum;
}

缺点：时间复杂度 O(n²)，适用于小规模数据。

方法2：Kadane’s Algorithm（O(n)）

思路：

• 动态规划思想：dp[i] 代表 以 nums[i] 结尾的最大子数组和。
• 递推公式：
  • dp[i] = max(dp[i-1] + nums[i], nums[i])
  • 只需维护 currentSum 变量，优化为 O(1) 空间。

public int maxSubArray(int[] nums) {
    int maxSum = nums[0], currentSum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(currentSum + nums[i], nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    return maxSum;
}

优点：

• 线性时间 O(n)，适用于 大规模数据。
• 适用于 金融、信号处理等领域。

总结

• 两数之和：HashMap 优化查询 O(n)
• 最长无重复子串：滑动窗口 O(n)
• 最大子数组和：Kadane’s Algorithm O(n)

🔥 掌握这些算法，快速提升算法面试能力！ 🚀