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

双指针技巧深度解析

news 2025/6/28 18:03:58

双指针技巧深度解析

- 基本概念
- 对撞指针的算法原理
- 典型案例分析与实现
- - 两数之和（有序数组）
  - 验证回文串
  - 盛最多水的容器
  - 三数之和
  - 复杂度分析
- 总结与扩展
- - 核心思想总结
  - 适用场景
  - 注意事项

双指针技巧广泛应用于数组、链表等线性数据结构的问题中，通过使用两个指针在数据结构中协同移动，可以高效地解决许多看似复杂的问题。本文我将全面介绍双指针的基本概念、算法原理、经典案例分析与实现。

基本概念

双指针技巧是指在遍历数据结构时，使用两个指针协同工作，从而在不需要额外空间的情况下优化时间复杂度。双指针通常分为以下两种类型：

对撞指针：两个指针分别从数组的两端开始向中间移动，直到相遇。适用于有序数组的问题。
快慢指针：两个指针以不同的速度移动，通常用于链表中的环检测、中间节点查找等问题。(主页搜索,有写过专题)

对撞指针的算法原理

对撞指针（Opposite Direction Pointers）通常用于解决有序数组或链表中的问题。基本思路是：

初始化两个指针，一个指向数组的起始位置（左指针），另一个指向数组的末尾位置（右指针）。
根据问题的条件，移动左指针向右或右指针向左。
当两个指针相遇时，遍历结束。

对撞指针的核心在于利用问题的特性（如数组有序），通过合理移动指针来减少不必要的遍历，从而将时间复杂度从 $O (n^{2})$ 优化到 $O (n)$ 。

典型案例分析与实现

两数之和（有序数组）

题目描述：给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。返回这两个数的下标（从1开始）。

解题思路：使用对撞指针，左指针指向数组起始位置，右指针指向数组末尾。如果两数之和小于目标值，左指针右移；如果大于目标值，右指针左移；如果相等，则找到结果。

public int[] twoSum(int[] numbers, int target) {int left = 0, right = numbers.length - 1;while (left < right) {int sum = numbers[left] + numbers[right];if (sum == target) {return new int[]{left + 1, right + 1}; // 下标从1开始} else if (sum < target) {left++; // 和太小，左指针右移} else {right--; // 和太大，右指针左移}}return new int[]{-1, -1}; // 没有找到符合条件的数对
}

验证回文串

题目描述：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

解题思路：使用对撞指针，左指针指向字符串的起始位置，右指针指向字符串的末尾。跳过非字母和数字的字符，比较两个指针指向的字符是否相等（忽略大小写）。

public boolean isPalindrome(String s) {int left = 0, right = s.length() - 1;while (left < right) {// 跳过非字母和数字的字符while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {left++;}while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {right--;}// 比较字符（忽略大小写）if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {return false;}left++;right--;}return true;
}

盛最多水的容器

题目描述：给定n个非负整数a₁,a₂,…,aₙ，每个数代表坐标中的一个点(i,aᵢ)。在坐标内画n条垂直线，垂直线i的两个端点分别为 $(i, a_{i})$ 和 $(i, 0)$ 。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

解题思路：使用对撞指针，左指针指向数组起始位置，右指针指向数组末尾。容器的容积由较短的垂直线和两指针之间的距离决定。每次移动较短的垂直线对应的指针，以寻找更大的容积。

public int maxArea(int[] height) {int left = 0, right = height.length - 1;int maxArea = 0;while (left < right) {int currentArea = Math.min(height[left], height[right]) * (right - left);maxArea = Math.max(maxArea, currentArea);// 移动较短的垂直线对应的指针if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;
}

三数之和

题目描述：给定一个包含 $n$ 个整数的数组nums，判断nums中是否存在三个元素 $a$ , $b$ , $c$ ，使得 $a + b + c = 0$ ？找出所有满足条件且不重复的三元组。

解题思路：先对数组进行排序，然后遍历数组，将每个元素作为三元组的第一个元素。对于每个元素，使用对撞指针在剩余元素中寻找另外两个元素，使得它们的和等于当前元素的相反数。

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();if (nums == null || nums.length < 3) {return result;}// 对数组进行排序Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n - 2; i++) {// 跳过重复的第一个元素if (i > 0 && nums[i] == nums[i - 1]) {continue;}int target = -nums[i];int left = i + 1, right = n - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {result.add(Arrays.asList(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 < target) {left++;} else {right--;}}}return result;
}