第1章数组与字符串

第1章：数组与字符串——两数之和、三数之和、最长无重复子串、字符串反转与回文判断

数组和字符串，几乎是每一场iOS面试的“开胃菜”。

说实话，这两类题目看似基础，但恰恰是区分“背答案”和“真理解”的分水岭。我面试过不少候选人，两数之和能秒写哈希表解法，但一问为什么不用暴力法，就卡住了。嗯，这章我们就来把这些高频题彻底讲透。

1.1 两数之和：从暴力到哈希的进化

题目很简单：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数的下标。

暴力法——双层循环，O(n²)时间复杂度。我刚开始刷题时也这么写，但有一次在项目里处理一个百万级的数据集，这种写法直接让App卡死了。从那以后，我对O(n²)的解法就特别敏感。

核心思路：用哈希表（Dictionary）存储“当前值”和“目标值的差值”。遍历一次数组，每次检查差值是否已在哈希表中。

// Swift 实现 - 两数之和
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var dict = [Int: Int]() // 值 -> 下标
    for (i, num) in nums.enumerated() {
        let complement = target - num
        if let index = dict[complement] {
            return [index, i]
        }
        dict[num] = i
    }
    return []
}

我的小技巧：面试时先提暴力法，再说“但我们可以优化到O(n)”。这能展示你的思考过程，而不是直接甩出最优解。

1.2 三数之和：双指针的经典应用

三数之和比两数之和难了一个档次。要求找出所有不重复的三元组，使得三个数之和为0。

我个人习惯先排序，再用双指针。为什么排序？因为排序后可以跳过重复元素，避免出现重复的三元组。

// Swift 实现 - 三数之和
func threeSum(_ nums: [Int]) -> [[Int]] {
    guard nums.count >= 3 else { return [] }
    let sorted = nums.sorted()
    var result = [[Int]]()
    
    for i in 0..<sorted.count - 2 {
        // 跳过重复的固定元素
        if i > 0 && sorted[i] == sorted[i - 1] { continue }
        
        var left = i + 1
        var right = sorted.count - 1
        
        while left < right {
            let sum = sorted[i] + sorted[left] + sorted[right]
            if sum == 0 {
                result.append([sorted[i], sorted[left], sorted[right]])
                // 跳过重复的左右指针
                while left < right && sorted[left] == sorted[left + 1] { left += 1 }
                while left < right && sorted[right] == sorted[right - 1] { right -= 1 }
                left += 1
                right -= 1
            } else if sum < 0 {
                left += 1
            } else {
                right -= 1
            }
        }
    }
    return result
}

避坑指南：我曾经在去重逻辑上栽过跟头。记住：固定元素去重用 i > 0 && sorted[i] == sorted[i-1]；左右指针去重要在找到一组解之后进行，而不是每次循环都去重。

1.3 最长无重复子串：滑动窗口的实战

这道题在iOS开发中其实很实用。比如处理用户输入的搜索关键词，或者解析网络数据流时，都需要检测无重复的连续子串。

核心思路是滑动窗口 + 哈希表。窗口右边界不断右移，左边界根据重复字符的位置动态调整。

// Swift 实现 - 最长无重复子串
func lengthOfLongestSubstring(_ s: String) -> Int {
    var charIndexMap = [Character: Int]() // 字符 -> 最近一次出现的下标
    var maxLength = 0
    var left = 0
    
    for (right, char) in s.enumerated() {
        // 如果字符已存在且在窗口内，移动左边界
        if let lastIndex = charIndexMap[char], lastIndex >= left {
            left = lastIndex + 1
        }
        charIndexMap[char] = right
        maxLength = max(maxLength, right - left + 1)
    }
    return maxLength
}

面试加分点：可以提一下空间复杂度。虽然用了哈希表，但字符集有限（ASCII 128个或Unicode），所以空间是O(1)级别的。面试官听到这个细节通常会点头。

1.4 字符串反转与回文判断

字符串反转在iOS里太常见了。比如UILabel显示从右到左的文本，或者处理某些加密算法。

最简单的反转：用Swift的reversed()方法。但面试时最好手写一个双指针版本，展示你的基本功。

// 手写字符串反转 - 双指针
func reverseString(_ s: inout [Character]) {
    var left = 0
    var right = s.count - 1
    while left < right {
        s.swapAt(left, right)
        left += 1
        right -= 1
    }
}

回文判断就更直接了。双指针从两端向中间走，遇到非字母数字字符就跳过。

// 验证回文串（忽略大小写和非字母数字）
func isPalindrome(_ s: String) -> Bool {
    let chars = Array(s.lowercased())
    var left = 0
    var right = chars.count - 1
    
    while left < right {
        // 跳过非字母数字
        while left < right && !chars[left].isLetter && !chars[left].isNumber {
            left += 1
        }
        while left < right && !chars[right].isLetter && !chars[right].isNumber {
            right -= 1
        }
        if chars[left] != chars[right] {
            return false
        }
        left += 1
        right -= 1
    }
    return true
}

总结一下这四道题的核心套路：

题目	核心技巧	时间复杂度	空间复杂度
两数之和	哈希表存差值	O(n)	O(n)
三数之和	排序 + 双指针	O(n²)	O(1) 或 O(n) 排序空间
最长无重复子串	滑动窗口 + 哈希表	O(n)	O(字符集大小)
字符串反转/回文	双指针	O(n)	O(1)

你想想看，这四道题其实都在训练同一个能力——如何用更少的遍历次数解决问题。从暴力到哈希，从哈希到双指针，再到滑动窗口，每一步优化都是对数据结构的更深理解。

我个人建议，把这四道题当作热身练习。每天写一遍，坚持一周，你的编码手感会有明显提升。下一章我们会聊链表相关的题目，那又是另一番天地了。

📚 课程目录