双指针技巧在数组算法中的应用与优化-开发者社区

1. 合并两个有序数组：从暴力到双指针的优化之路

合并两个有序数组是算法面试中的经典问题，看似简单却暗藏玄机。我们先来看最直观的解法：直接将nums2拼接到nums1末尾，然后调用排序函数。这种方法在C++中可以这样实现：

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for(int i = 0; i<n; i++){ nums1[m+i] = nums2[i]; } sort(nums1.begin(),nums1.end()); } };

这种解法的时间复杂度是O((m+n)log(m+n))，主要消耗在排序步骤。虽然简单直接，但面试官更希望看到你能利用数组已排序的特性进行优化。

1.1 双指针法的精妙之处

双指针法才是这道题的正解。我们设置三个指针：

p1指向nums1的末尾（即第m个元素）
p2指向nums2的末尾（即第n个元素）
p指向nums1的最终位置（即第m+n个元素）

class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int p1 = m - 1, p2 = n - 1; int p = m + n - 1; while(p1 >= 0 && p2 >= 0){ nums1[p--] = (nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--]; } while(p2 >= 0){ nums1[p--] = nums2[p2--]; } } };

这种解法的时间复杂度是O(m+n)，空间复杂度是O(1)，完美利用了nums1末尾的空闲空间。

关键点：从后向前填充可以避免覆盖nums1中尚未处理的元素，这是很多初学者容易忽略的细节。

2. 移除元素：快慢指针的艺术

移除元素问题要求原地修改数组，这提示我们需要使用双指针技巧。快指针遍历数组，慢指针记录有效位置。

2.1 标准双指针解法

class Solution { public: int removeElement(vector<int>& nums, int val) { int slow = 0; for(int fast = 0; fast < nums.size(); fast++){ if(nums[fast] != val){ nums[slow++] = nums[fast]; } } return slow; } };

这种解法的时间复杂度是O(n)，空间复杂度是O(1)。但面试官可能会问：如果val元素很少，这种方法会做很多不必要的复制，有没有优化空间？

2.2 优化解法：交换移除

当遇到val时，我们可以将其与数组末尾元素交换，并缩小数组范围：

class Solution { public: int removeElement(vector<int>& nums, int val) { int left = 0, right = nums.size(); while(left < right){ if(nums[left] == val){ nums[left] = nums[right-1]; right--; }else{ left++; } } return left; } };

这种解法在val元素较少时效率更高，因为它减少了元素移动次数。

3. 删除有序数组中的重复项：双指针的变种

这个问题要求每个元素只出现一次，是双指针的经典应用场景。

3.1 基础解法

class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.empty()) return 0; int slow = 0; for(int fast = 1; fast < nums.size(); fast++){ if(nums[fast] != nums[slow]){ nums[++slow] = nums[fast]; } } return slow + 1; } };

时间复杂度O(n)，空间复杂度O(1)。关键在于理解slow指针始终指向最后一个不重复的元素。

3.2 边界情况处理

需要注意空数组和单元素数组的特殊情况：

空数组直接返回0
单元素数组直接返回1

4. 删除有序数组中的重复项 II：允许两次重复

这个问题是前一个问题的升级版，允许元素最多出现两次。

4.1 通用解法

class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size() <= 2) return nums.size(); int slow = 2; for(int fast = 2; fast < nums.size(); fast++){ if(nums[fast] != nums[slow-2]){ nums[slow++] = nums[fast]; } } return slow; } };

这个解法的精妙之处在于比较nums[fast]和nums[slow-2]，确保最多只保留两个相同元素。

4.2 扩展思考

如果要保留最多k个相同元素，可以将解法抽象为：

int removeDuplicatesK(vector<int>& nums, int k) { if(nums.size() <= k) return nums.size(); int slow = k; for(int fast = k; fast < nums.size(); fast++){ if(nums[fast] != nums[slow-k]){ nums[slow++] = nums[fast]; } } return slow; }

这种抽象思维在面试中很加分，展示了解决一类问题的能力。

5. 多数元素：摩尔投票法的神奇

多数元素问题要求找出出现次数超过⌊n/2⌋的元素，摩尔投票法是最优解。

5.1 摩尔投票法解析

class Solution { public: int majorityElement(vector<int>& nums) { int candidate = nums[0], count = 1; for(int i = 1; i < nums.size(); i++){ if(count == 0){ candidate = nums[i]; count = 1; }else if(candidate == nums[i]){ count++; }else{ count--; } } return candidate; } };

时间复杂度O(n)，空间复杂度O(1)。算法核心思想是"多数元素的数量比其他所有元素数量之和还多"。