算法解释：
双指针指的是在一定范围内（比如说数组），有两个指针指向不同的元素从而协同完成任务，一般是需要找出该段范围的一个或两个甚至多个元素以满足需求。
- 两个指针运动方向相反：当满足XXX条件时，左指针右移或者右指针左移，循环条件一般为
left<=right - 两个指针运动方向相同：一般两个指针的运动速度不同（比如说Floyd判圈法）
练习
1. 删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
自己写的双循环遍历代码（运行性能较低）：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
bool flag = false;
int count=0;
vector<int>::iterator vIter = nums.begin();
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
// if(i==j) {break;}
if(nums[i]==nums[j]){
flag = true;
nums.erase(vIter+j);
j--;
}
}
if(flag){
count++;
flag = false;
}
}
// printf("nums = [");
// for(int i=0;i<nums.size();i++){
// cout << nums[i] << ((i==nums.size()-1)?"]":",");
// }
return nums.size();
}
};
题解用的双指针，个人感觉就是一趟做完双循环要做的事
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 1,fast=1;
while(fast<nums.size()){
if(nums[fast-1]!=nums[fast]){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
2. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
个人感觉和上一题差不多，就是需要注意这里while的终止条件是小于等于
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow=0,fast=1,n = nums.size();
while(fast<=n){
if(nums[fast-1]!=val){
nums[slow] = nums[fast-1];
slow++;
}
fast++;
}
return slow;
}
};
3. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
输入: [1,3,5,6], 2
输出: 1
输入: [1,3,5,6], 7
输出: 4
我的思路：暴力求解，即按顺序找下去并判断多种情况
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int fast = 1,n = nums.size();
if(n==0){
return 0;
}
if(n==1){
return (nums[0]<target)?1:0;
}
while(fast<n){
if(nums[fast-1]==target){
return fast-1;
}
if(nums[fast]==target){
return fast;
}
if(nums[fast-1] < target && nums[fast]>target){
return fast;
}
if(nums[fast-1] < target && fast+1 == n){
return fast+1;
}
fast++;
}
return 0;
}
};
题解：二分法
tip: 有排序数组就可考虑使用二分法
4. 两数之和 II - 输入有序数组
【Leetcode 167. 两数之和 II - 输入有序数组】
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size()-1;
while(left <= right){
int mid = ((left+right)>>1) + 1; //此处注意(left+right)>>1外面一定要用括号括起来
if(numbers[mid] >= target) right = mid;
if(numbers[left] + numbers[right] > target) right--;
else if(numbers[left] + numbers[right] == target) break;
else left++;
}
return vector<int>{left+1,right+1}; // return 语句一定要在while外面，因为函数要求返回该类型
}
};
5. 归并两个有序数组
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int pos=m+n-1,i=m-1, j=n-1;
while(i >= 0 && j >= 0){
nums1[pos--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
}
while(pos >= 0){
nums1[pos--] = (i>=0)?nums1[i--]:nums2[j--];
}
}
};
6. 快慢指针-环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow =head, *fast = head;
do{
if(!fast || !fast->next) return nullptr;
fast = fast->next->next;
slow = slow->next;
}while(slow != fast);
fast = head;
while(slow != fast){
slow = slow->next;
fast = fast->next;
}
return fast;
}
};
7. 平方数之和
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
示例 1：
输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5
示例 2：
输入：c = 3
输出：false
示例 3：
输入：c = 4
输出：true
示例 4：
输入：c = 2
输出：true
示例 5：
输入：c = 1
输出：true
class Solution {
public:
bool judgeSquareSum(int c) {
int right = (int)sqrt(c), left = 0;
while(left <= right){
int sum = c; //注意： 加操作，即left*left+right*right很可能会溢出，故改为减操作
sum -= right*right;
sum -= left*left;
if(sum < 0) right--;
else if(sum > 0) left++;
else return true;
}
return false;
}
};
8. 验证回文字符串 Ⅱ
680. 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: s = "aba"
输出: true
示例 2:
输入: s = "abca"
输出: true
解释: 你可以删除c字符。
示例 3:
输入: s = "abc"
输出: false
class Solution {
public:
bool isPalindrome(int left, int right, string s){
for(int i=left,j=right; i <= j; i++, j--){ // 注意符号的使用：还是三个";"不变，只不过多条件用","隔开
if(s[i] != s[j]) return false;
}
return true;
}
bool validPalindrome(string s) {
int right = s.size()-1, left = 0;
int cnt = 0;
while(left <= right){
// if(cnt > 1 || (cnt==1 && s.size() == 3)) return false;
if(s[left] != s[right]){
// cnt++; //cnt初值为0，用来记录删除字母的个数
// if(s[left+1] == s[right]) left++;
// else if(s[left] == s[right-1]) right--;
// 这样子判断不对，很有可能两个条件都满足，但是方向选择不对会影响到后面的判断
return isPalindrome(left+1,right,s) || isPalindrome(left,right-1,s); //注意传参数的时候left+1和left++，right-1和right-1的区别
}else{
left++;
right--;
}
}
return true;
}
};