下面是对双指针算法的题目总结和归纳，有需要借鉴即可。
1.移动零
题目链接：LINK
题解：
- 思路①：暴力求解
- 详述：碰到0，后面所有数字往前挪动一位；碰到非0不用管。
- 时间复杂度：O(N^2)
- 思路②：双指针算法
- 详述：定义两个指针pcur和pdest，pcur起始位置在0下标处，用来遍历数组；pdest起始位置在-1.用来保留要交换数字的下标；如果pcur遇到非0，那就dest与pcur位置的值进行交换，如果是0，pcur继续向后走，不做处理。
- 时间复杂度：O(N)
class Solution { public: void Swap(int& x,int& y) { int temp = x; x = y; y = temp; } void moveZeroes(vector<int>& nums) { int pcur = 0; int pdest = -1; while(pcur < nums.size())//遍历完成就结束 { //不是0，我们就换一下 if(nums[pcur] != 0) { Swap(nums[++pdest],nums[pcur]); } pcur++; } } };
2.复写零
题目链接：LINK
题解：
- 思路①：暴力求解
- 详述：定义一个指针，一个pcur，扫描，如果pcur找到的是非0，那就不用管，；如果pcur找到的是0，那就把该数组所有元素往后移动一位，并且把该位置置为0。
- 复杂度：O(N^2)
- 思路②：双指针法
- 详述：定义两个指针，先大致模拟一下最后pcur和dest最后结果在哪，然后从后向前进行复写。
- 复杂度：O(N)
class Solution { public: void duplicateZeros(vector<int>& arr) { int cur = 0,dest = -1,n = arr.size(); //1.先找到cur和dest应该指向的位置 while(cur < n) { if(arr[cur])//非0 { dest++; } else { dest+=2; } if(dest>=n-1)//终止条件：dest到达最后一个地方或者说超出了 { break; } cur++; } //2.处理一下特殊情况 if(dest == n) { arr[--dest] = 0; cur--; dest--; } //3.依次赋值 while(cur>=0) { if(arr[cur])//如果说是非0 { arr[dest--] = arr[cur--]; } else//如果说是0 { arr[dest--] = 0; arr[dest--] = 0; cur--; } } } };
3.快乐数
题目链接：LINK
题解：
- 思路①：双指针算法
- 详述：定义一个slow指针，每次算一次；定义一个fast指针，每次算两步，当slow == fast且是1时候则返回true；如果slow==fast且不是1，则返回false；
- 时间复杂度：O(N)
class Solution { public: int bitsum(int n) { int sum = 0; while(n) { sum+=(n%10)*(n%10); n/=10; } return sum; } bool isHappy(int n) { //1.定义两个指针 int slow = bitsum(n); int fast = bitsum(bitsum(n)); while(slow != fast) { slow = bitsum(slow); fast = bitsum(bitsum(fast)); } return slow == 1; } };
4.盛最多水的容器
题目链接：LINK
题解：
- 思路①：暴力求解
- 详述：定义两个指针，依次枚举，取最大值
- 时间复杂度：O(N^2)
- 思路②：双指针算法
- 详述：定义两个指针，一个指向0下标处，另一个指向最后一个下标处，算出此时容器体积大小，然后如果left指针小，则left++，如果right小，则right–，依次类推，找出其中的最大值就好。
- 时间复杂度：O(N)
class Solution { public: int maxArea(vector<int>& height) { int first = 0,last = height.size()-1,ret = 0; while(first<last) { ret = max(ret,(last - first) * min(height[first],height[last])); //移动指针 if(height[first] < height[last]) { first++; } else { last--; } } return ret; } };
5.有效三角形的个数
题目链接：LINK
题解：
- 思路①：暴力求解
- 详述：一次列举各种情况，进行求证即可。
- 时间复杂度：O(N^3)
- 思路②：双指针算法
- 详述：开始首先排序，再固定一个后面的大数，再定义两个指针，如果left+right处的值大于固定的数，那么就直接加上个数，如果小，就left++即可，以此类推。
- 时间复杂度：O(N^2)
class Solution { public: int triangleNumber(vector<int>& nums) { //先排序 sort(nums.begin(),nums.end()); //定义三个指针，一个用来固定位置，另外两个用来找 int count = 0; for(int i = nums.size() - 1;i>=2;i--)//先固定一个数字 { int left = 0; int right = i - 1; while(left < right) { if(nums[left] + nums[right] > nums[i]) { count += right - left; right--; } else { left++; } } } return count; } };
6.和为s的两个数
题目链接：LINK
题解：
- 思路①：暴力求解
- 详述：依次枚举，返回正确的数字
- 时间复杂度：O(N^2)
- 思路②：双指针算法
- 详述：left在最左端，right在最右端，sum太大，right–，sum太小，left++，sum==s，返回
- 时间复杂度：O(N)
class Solution { public: vector<int> twoSum(vector<int>& price, int target) { //定义两个指针，大了调小，小了调大，等于返回 int left = 0,right = price.size() - 1; while(left < right) { if((price[left] + price[right]) < target) { left ++; } else if((price[left] + price[right]) > target) { right --; } else { return {price[left] , price[right]} ; } } return {0,0}; } };
7.三数之和
题目链接：LINK
题解：
- 思路①：暴力求解
- 详述：依次枚举，三重循环
- 时间复杂度：O(N^3)
- 思路②：双指针算法
- 详述：固定一个数a，left在左端，right在右端，看sum与-a的大小，若sum较大，right–，如果sum较小，那就left++…同时还应该注意去重问题。
- 时间复杂度：O(N^2)
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; //排序 sort(nums.begin(),nums.end()); // for(int i = 0;i<nums.size();)//先固定一个数 { int left = i + 1,right = nums.size() - 1,target = -nums[i]; if(target < 0) { break; } while(left < right) { int sum = nums[left] + nums[right]; if(sum > target) { right--; } else if(sum < target) { left++; } else { ret.push_back({nums[i],nums[left],nums[right]}); left++,right--; //去重 while(left<right && nums[left] == nums[left-1]) { left++; } while(right>left && nums[right] == nums[right+1]) { right--; } } } i++; while(i < nums.size() && nums[i] == nums[i-1]) { i++; } } return ret; } };
8.四数之和
题目链接：LINK
题解：
- 思路①：暴力求解
- 详述：依次枚举，四层循环
- 时间复杂度：O(N^4)
- 思路②：双指针算法
- 详述：先固定一个数字，再借鉴”三数之和“的思路
- 时间复杂度：O(N^3)
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> ret; int n = nums.size(); for (int a = 0; a < n;)//固定数a { for (int b = a + 1; b < n;)//固定数b { int left = b + 1, right = n - 1; long long LFtarget = (long long)target - nums[a] - nums[b]; while (left < right) { int LFsum = nums[left] + nums[right]; if (LFsum > LFtarget) { right--; } else if (LFsum < LFtarget) { left++; } else { ret.push_back({ nums[a],nums[b],nums[left],nums[right] }); left++, right--; //去重 left and right while (left < right && nums[left] == nums[left - 1]) { left++; } while (left < right && nums[right] == nums[right + 1]) { right--; } }//end else }//end left and right while b++; while (b < n && nums[b] == nums[b - 1]) { b++; } }//end b while a++; while (a < n && nums[a] == nums[a - 1]) { a++; } }// end a while return ret; } };
EOF
