算法笔记：回文串验证与有序数组两数之和

"算法笔记_12.16-12.22，包括验证回文串和两数之和II的算法题解" 在本周的算法笔记中，我们探讨了两种基于数组的常见问题：验证回文串和两数之和II。首先，让我们详细解析这两个问题及其解决方案。 1. 验证回文串 问题描述：给定一个字符串，我们需要判断它是否是回文串，即忽略大小写和非字母数字字符后，字符串正读和反读是一样的。这里，空字符串也被认为是有效的回文串。 解法：双指针法 - 初始化两个指针，一个从字符串的开头（i1），另一个从字符串的结尾（i2）。 - 使用循环，当i1 < i2时，检查指针所指向的字符是否为字母或数字。如果不是，则移动该指针（i1 向右，i2 向左）。如果都是，比较两个字符是否相等，如果不等则返回false，表示不是回文串。 - 当i1 >= i2时，说明字符串是回文串，返回true。 代码实现： ```cpp class Solution { public: bool isPalindrome(string s) { int i1 = 0; int i2 = s.size() - 1; while (i1 < i2) { while (!is_char(s[i1]) && (i1 < i2)) ++i1; while (!is_char(s[i2]) && (i1 < i2)) --i2; if (s[i1] != s[i2]) return false; ++i1; --i2; } return true; } }; ``` 时间复杂度：O(n)，只扫描一遍字符串。 空间复杂度：O(1)，无需额外空间。 2. 两数之和II - 输入有序数组 问题描述：给定一个升序排列的数组，找出两个数，使得它们的和等于目标数，并返回它们的下标（从1开始计数）。 解法：双指针法（对撞指针） - 初始化两个指针，一个指向数组的起始位置（i），另一个指向数组的末尾（j）。 - 使用循环，当i < j时，检查当前两数之和（numbers[i] + numbers[j]）是否等于目标数。如果是，返回{i+1, j+1}作为结果。如果和小于目标数，将左指针i向右移动一位（数组升序，增加和）。如果和大于目标数，将右指针j向左移动一位（减少和）。 - 如果遍历完数组没有找到符合条件的组合，说明不存在这样的组合。 代码实现： ```cpp class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int i = 0, j = numbers.size() - 1; while (i < j) { if (numbers[i] + numbers[j] == target) { return {i + 1, j + 1}; } else if (numbers[i] + numbers[j] < target) { ++i; } else { --j; } } return {}; // 不存在符合条件的组合 } }; ``` 时间复杂度：O(n)，最坏情况下需要遍历整个数组。 空间复杂度：O(1)，无需额外空间。 总结，这两道题目都展示了双指针法在解决数组问题中的高效性。对于验证回文串，双指针从两端向中心靠近，简化了问题处理；而对于两数之和II，对撞指针法充分利用了有序数组的特点，有效地减少了搜索范围。这些算法思想在实际编程中非常实用，值得深入理解和掌握。