双指针在C++中的应用：深入解析与实例

在C++编程中，双指针（Two Pointers）是一种常见且高效的算法技巧。通过使用两个指针在数组或链表中移动，可以解决许多复杂的问题。本文将详细介绍双指针在C++中的应用，并列举一些经典的应用场景。

双指针的基本概念

双指针的核心思想是通过两个指针在数据结构中移动，来减少时间复杂度。通常，一个指针用于遍历数据结构，另一个指针则根据特定的条件进行移动。双指针可以分为以下几种类型：

快慢指针：一个指针移动速度快，另一个移动速度慢，常用于检测链表中的环或寻找链表的中点。
左右指针：两个指针从数组的两端向中间移动，常用于排序、查找等问题。
滑动窗口：通过移动窗口的左右边界来解决子数组或子字符串的问题。

双指针的应用场景

链表操作

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

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

寻找链表中点：快指针移动速度是慢指针的两倍，当快指针到达末尾时，慢指针刚好在中点。

ListNode* findMiddle(ListNode *head) {
  if (!head) return nullptr;
  ListNode *slow = head, *fast = head;
  while (fast->next && fast->next->next) {
      slow = slow->next;
      fast = fast->next->next;
  }
  return slow;
}

数组操作

两数之和：使用左右指针从数组两端向中间移动，寻找和为目标值的两个数。

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

三数之和：固定一个数，然后用双指针在剩余数组中寻找另外两个数。

vector<vector<int>> threeSum(vector<int>& nums) {
  sort(nums.begin(), nums.end());
  vector<vector<int>> result;
  for (int i = 0; i < nums.size() - 2; 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;
}

字符串处理

回文字符串：使用左右指针从字符串两端向中间移动，判断是否为回文。

bool isPalindrome(string s) {
  int left = 0, right = s.length() - 1;
  while (left < right) {
      while (left < right && !isalnum(s[left])) left++;
      while (left < right && !isalnum(s[right])) right--;
      if (tolower(s[left]) != tolower(s[right])) return false;
      left++; right--;
  }
  return true;
}

总结

双指针技术在C++中广泛应用于各种数据结构和算法问题中。通过巧妙地移动指针，可以大大减少时间复杂度，提高代码的效率。无论是链表、数组还是字符串处理，双指针都能提供简洁而高效的解决方案。希望本文能帮助大家更好地理解和应用双指针技术，解决实际编程中的问题。