算法学习 双指针技巧总结

一、快慢指针常见算法

1.判断链表中是否有环

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

	/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr)
            return false;
        
        ListNode* p_fast=head;
        ListNode* p_slow=head;
        while(p_fast!=nullptr)
        {
            p_fast=p_fast->next;
            if(p_fast!=nullptr)p_fast=p_fast->next;
            p_slow=p_slow->next;
            if(p_fast==p_slow)
                return true;
        }
        return false;
    }
};
改进代码

```cpp
class Solution {
public:
bool hasCycle(ListNode* head) 
{
	//两个运动员位于同意起点head
	ListNode* faster{ head };  //快的运动员
	ListNode* slower{ head };  //慢的运动员

	if (head == NULL)  //输入链表为空，必然不是循环链表
		return false;

	while (faster != NULL && faster->next != NULL)
	{
		faster = faster->next->next;  //快的运动员每次跑两步
		slower = slower->next;  //慢的运动员每次跑一步
		if (faster == slower)  //他们在比赛中相遇了
			return true;  //可以断定是环形道，直道不可能相遇
	}
	return false;  //快的运动员到终点了，那就是直道，绕圈跑不会有终点
}
};

2.环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
进阶：
你是否可以不用额外空间解决此题？

可以看到，当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。这是为什么呢？
第一次相遇时，假设慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步，也就是说比 slow 多走了 k 步（环长度的倍数）。

设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。
巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。

所以，只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后就会相遇，相遇之处就是环的起点了。

/**
 * 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) {
        if(head==nullptr)
            return head;
        ListNode* fast=head;
        ListNode*slow=head;
        while(fast!=nullptr&&fast->next!=nullptr)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast)
            {
                slow=head;
                while(slow!=fast)
                {
                 slow=slow->next;
                 fast=fast->next;
                }
                return slow;
            }
        }
       
        return nullptr;
    }
};

3.寻找链表的中点

类似上面的思路，我们还可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
}
// slow 就在中间位置
return slow;

当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右：
center
寻找链表中点的一个重要作用是对链表进行归并排序。
回想数组的归并排序：求中点索引递归地把数组二分，最后合并两个有序数组。对于链表，合并两个有序链表是很简单的，难点就在于二分。
但是现在你学会了找到链表的中点，就能实现链表的二分了。关于归并排序的具体内容本文就不具体展开了。

4.寻找链表的倒数第k个元素

我们的思路还是使用快慢指针，让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点（为了简化，假设 k 不会超过链表长度）：

ListNode slow, fast;
slow = fast = head;
while (k-- > 0) 
    fast = fast.next;

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

二、左右指针的常用算法

左右指针在数组中实际是指两个索引值，一般初始化为 left = 0, right = nums.length - 1 。

1.二分查找

2.两数之和

只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 可以调整 sum 的大小

int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            // 题目要求的索引是从 1 开始的
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    return new int[]{-1, -1};
}

3.反转数组

void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

4.滑动窗口

这也许是双指针技巧的最高境界了，如果掌握了此算法，可以解决一大类子字符串匹配的问题，不过「滑动窗口」稍微比上述的这些算法复杂些。

幸运的是，这类算法是有框架模板的，而且这篇文章就讲解了「滑动窗口」算法模板，帮大家秒杀几道 LeetCode 子串匹配的问题。

5.两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

1. 排序+双指针

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()==0||nums2.size()==0)
            return vector<int>{};
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        int nums1_left=0;
        int nums2_left=0;
        vector<int>ret;
        while(nums1_left<nums1.size()&&nums2_left<nums2.size())
        {
            if(nums1[nums1_left]==nums2[nums2_left])
            {
                 ret.push_back(nums1[nums1_left]);
                nums1_left++;
                nums2_left++;
            }else if(nums1[nums1_left]>nums2[nums2_left])
                nums2_left++;
            else
                nums1_left++;
        }
     return ret;
    }
};

2. 哈希表

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()==0||nums2.size()==0)
            return vector<int>{};
            vector<int>ret;
        unordered_map<int,int>hash;
        for(int i=0;i<nums1.size();i++)
        {
            auto ptr=hash.find(nums1[i]);
            if(ptr==hash.end())
            {
                hash.insert(make_pair(nums1[i],1));
            }else
                ptr->second++;
        }
        for(int i=0;i<nums2.size();i++)
        {
            auto ptr=hash.find(nums2[i]);
            if(ptr==hash.end())
                continue;
            else if(ptr->second==0)
                continue;
            else{
                ret.push_back(ptr->first);
                ptr->second--;
            }
        }

        return ret;
    }
};

最后

以上就是鲤鱼巨人为你收集整理的算法学习 双指针技巧总结的全部内容，希望文章能够帮你解决算法学习 双指针技巧总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。