当前位置：首页 > news >正文

楚风网站建设工作室/微信加精准客源软件

news 2025/7/3 19:34:57

楚风网站建设工作室,微信加精准客源软件,2018什么语言做网站比较好,活动策划案格式模板和范文双指针（Two Pointers）是一种常用的算法思想，通过使用两个指针（通常是下标或迭代器）在数组、链表或字符串中协同工作，高效解决一些问题。双指针的核心思想是通过指针的移动来减少时间复杂度，通常…

双指针（Two Pointers）是一种常用的算法思想，通过使用两个指针（通常是下标或迭代器）在数组、链表或字符串中协同工作，高效解决一些问题。双指针的核心思想是通过指针的移动来减少时间复杂度，通常将暴力解法的 O(n²) 优化为 O(n)。

1. 双指针的常见形式

双指针的常见形式包括：

左右指针：
- 两个指针从两端向中间移动。
- 适用于有序数组或字符串的问题（如两数之和、反转字符串等）。
快慢指针：
- 两个指针以不同的速度移动。
- 适用于链表问题（如判断链表是否有环、找到链表的中间节点等）。
滑动窗口：
- 两个指针同向移动，维护一个窗口。
- 适用于子数组或子字符串问题（如最短/最长子数组、无重复字符子串等）。

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 {};
}

反转字符串：

给定一个字符数组，将其反转。

代码实现：

void reverseString(vector<char>& s) {int left = 0, right = s.size() - 1;while (left < right) {swap(s[left], s[right]);left++;right--;}
}

3. 快慢指针

核心思想

两个指针以不同的速度移动，通常用于链表问题。
快指针每次移动两步，慢指针每次移动一步。

经典问题

判断链表是否有环：

使用快慢指针，如果快指针追上慢指针，则链表有环。

代码实现：

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

找到链表的中间节点：

快指针到达链表末尾时，慢指针正好在中间。

代码实现：

ListNode* middleNode(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;
}

4. 滑动窗口

核心思想

两个指针同向移动，维护一个窗口。
适用于子数组或子字符串问题。

经典问题

无重复字符的最长子字符串：

找到不包含重复字符的最长子字符串。

代码实现：

int lengthOfLongestSubstring(string s) {int left = 0, right = 0;int max_len = 0;unordered_set<char> window;while (right < s.size()) {if (window.find(s[right]) == window.end()) {window.insert(s[right]);max_len = max(max_len, right - left + 1);right++;} else {window.erase(s[left]);left++;}}return max_len;
}

和大于等于目标值的最短子数组：

找到和大于等于目标值的最短子数组。

代码实现：

int minSubArrayLen(int target, vector<int>& nums) {int left = 0, right = 0;int sum = 0;int min_len = INT_MAX;while (right < nums.size()) {sum += nums[right];while (sum >= target) {min_len = min(min_len, right - left + 1);sum -= nums[left];left++;}right++;}return min_len == INT_MAX ? 0 : min_len;
}