双指针c++

双指针（Two Pointers）是一种常用的算法技巧，通常用于解决数组或链表中的问题，如滑动窗口、区间合并、有序数组的两数之和等。双指针的核心思想是通过两个指针的移动来优化时间复杂度，通常可以将 (O(n^2)) 的暴力解法优化到 (O(n))。

以下是双指针的常见模板和示例：

1. 双指针的基本模板

1.1 同向双指针

特点：两个指针从同一侧开始移动，通常用于滑动窗口问题。

模板：

int twoPointersSameDirection(vector<int>& nums) {int left = 0, right = 0; // 初始化指针while (right < nums.size()) {// 扩展右边界right++;// 根据条件收缩左边界while (/* 不满足条件 */) {left++;}// 更新结果}return result;
}

1.2 对向双指针

特点：两个指针从两侧向中间移动，通常用于有序数组的问题。

模板：

int twoPointersOppositeDirection(vector<int>& nums) {int left = 0, right = nums.size() - 1; // 初始化指针while (left < right) {// 根据条件移动指针if (/* 满足条件 */) {left++;} else {right--;}// 更新结果}return result;
}

2. 常见应用场景

2.1 滑动窗口

问题描述：找到一个满足条件的子数组或子字符串。

示例：求最长无重复字符的子字符串。

int lengthOfLongestSubstring(string s) {int left = 0, right = 0; // 滑动窗口的左右边界unordered_set<char> window; // 记录窗口内的字符int maxLen = 0;while (right < s.size()) {char c = s[right];// 如果字符已存在，移动左边界while (window.count(c)) {window.erase(s[left]);left++;}// 扩展右边界window.insert(c);right++;// 更新结果maxLen = max(maxLen, right - left);}return maxLen;
}

2.2 有序数组的两数之和

问题描述：在有序数组中找到两个数，使它们的和等于目标值。

示例：

vector<int> twoSum(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {return {left, right};} else if (sum < target) {left++;} else {right--;}}return {}; // 未找到
}

2.3 区间合并

问题描述：合并所有重叠的区间。

示例：

vector<vector<int>> mergeIntervals(vector<vector<int>>& intervals) {if (intervals.empty()) return {};// 按区间起点排序sort(intervals.begin(), intervals.end());vector<vector<int>> merged;int left = intervals[0][0], right = intervals[0][1];for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] <= right) {// 合并区间right = max(right, intervals[i][1]);} else {// 保存当前区间merged.push_back({left, right});// 更新指针left = intervals[i][0];right = intervals[i][1];}}// 保存最后一个区间merged.push_back({left, right});return merged;
}

2.4 三数之和

问题描述：在数组中找到所有不重复的三元组，使它们的和等于目标值。

示例：

vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> result;for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重int left = i + 1, right = nums.size() - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {result.push_back({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;
}

2.5 链表的快慢指针

问题描述：判断链表是否有环，或找到链表的中间节点。

示例：判断链表是否有环。

bool hasCycle(ListNode* head) {if (!head || !head->next) return false;ListNode* slow = head;ListNode* fast = head->next;while (fast && fast->next) {if (slow == fast) return true;slow = slow->next;fast = fast->next->next;}return false;
}