algorithms►leetcode

003-无重复字符最长字串（滑动窗口）

无重复字符的最长子串

问题描述

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

示例

  • 输入: “abcabcbb”
    输出: 3
    解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
  • 输入: “bbbbb”
    输出: 1
    解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
  • 输入: “pwwkew”
    输出: 3
    解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

解决方案

滑动窗口法

这是一个经典的滑动窗口问题。我们可以使用哈希集合来记录当前窗口中的字符，并通过移动窗口的左右边界来寻找最长子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function lengthOfLongestSubstring(s) {
    let charSet = new Set();
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < s.length; right++) {
        // 当遇到重复字符时，移动左指针
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        // 添加当前字符到集合
        charSet.add(s[right]);
        // 更新最大长度
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

算法分析

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

可视化总结

a b c a b c b b
[---]           → "abc" (长度3)
  [---]         → "bca" (长度3)
    [---]       → "cab" (长度3)
        [-]     → "cb" (长度2)
          [ ]   → "b" (长度1)
            [ ] → "b" (长度1)
algorithms►leetcode

004-三数之和（双指针）

三数之和问题

三数之和（3Sum）是一个经典的算法问题，通常描述为：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a, b, c，使得 a + b + c = 0？找出所有满足条件且不重复的三元组。

解决方案

方法一：排序 + 双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function threeSum(nums) {
    // 1. 首先对数组进行排序
    nums.sort((a, b) => a - b);
    const result = [];
    const n = nums.length;
    
    // 2. 外层循环，固定第一个数
    for (let i = 0; i < n - 2; i++) {
        // 3. 跳过重复的第一个数
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        // 4. 初始化双指针
        let left = i + 1;
        let right = n - 1;
        
        // 5. 内层循环，使用双指针寻找另外两个数
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            
            if (sum < 0) {
                // 6. 和太小，移动左指针增大和
                left++;
            } else if (sum > 0) {
                // 7. 和太大，移动右指针减小和
                right--;
            } else {
                // 8. 找到有效三元组
                result.push([nums[i], nums[left], nums[right]]);
                
                // 9. 跳过重复的left和right值
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                
                // 10. 移动指针继续寻找
                left++;
                right--;
            }
        }
    }
    return result;
}
```

算法分析

  1. 时间复杂度：O(n²) - 排序需要 O(n log n)，双指针遍历需要 O(n²)
  2. 空间复杂度：O(1) 或 O(n) - 取决于排序算法的实现

关键点总结

  1. 排序：使我们可以使用双指针技巧

  2. 外层循环：固定第一个数nums[i]

  3. 内层双指针：

    • left从i+1开始
    • right从数组末尾开始

  4. 和的计算：

    • sum < 0 → 需要更大的数 → left++
    • sum > 0 → 需要更小的数 → right–
    • sum = 0 → 找到解

  5. 跳过重复：确保结果中没有重复的三元组

通过这样一步步的图解，你应该能更清楚地理解三数之和的解法了。