双指针算法思想：
双指针嘛，顾名思义，就是用两个指针来操作数据结构，通常是数组或链表。这两个指针可以有不同的角色，比如一个快、一个慢，或者一个从左往右走，一个从右往左走。这种技术的核心思想是通过两个指针的协作来解决问题，避免暴力枚举，从而提高效率。
实战
注意，为锻炼双指针思想，一定要用双指针的方法解题！！！
一、对撞指针：
对撞指针——这个很好理解，两个指针从数组的两端开始，逐步向中间移动。比如在排序数组中找两个数的和等于目标值，这种情况下用对撞指针特别方便。一个指针指向左边，一个指针指向右边，根据当前的和调整指针的位置。下面用一道题来举例。
二、快慢指针：
这个我挺熟悉的，通常是一个指针走得快，另一个走得慢。比如链表问题里，快指针每次走两步，慢指针每次走一步，这样就能用来找链表的中点或者判断是否有环。
三、滑动窗口：
滑动窗口——这个稍微复杂一点，但本质上还是两个指针在操作一个窗口的左右边界。比如在数组中找满足某种条件的最大子数组，滑动窗口可以动态调整窗口的大小，找到最优解。
( •̀ ω •́ )✧点击这里，继续学习其他模块吧！
题目汇集
一、对撞指针：
对撞指针——这个很好理解，两个指针从数组的两端开始，逐步向中间移动。比如在排序数组中找两个数的和等于目标值，这种情况下用对撞指针特别方便。一个指针指向左边，一个指针指向右边，根据当前的和调整指针的位置。下面用一道题来举例。
题目: 巧克力
问题描述
由于 Setsuna 和 myworld 两位同学在队内测试中 akak 了比赛，所以 Wiki 老师决定奖励他们。但是，这两位同学作为校内顶级 acmersacmers，Wiki 老师觉得奖励也必须要和算法挂钩。
现在已知 Wiki 老师有 nn 个盒子，已知每个盒子里面有 aiai 块巧克力，盒子按照 1,2,3...n1,2,3...n 的编号顺序从左往右依次摆放在 301301 训练基地的桌子上。
Setsuna 可以从左往右选择 kk 个盒子（编号 11 到编号 kk），myworld 可以从右往左选 mm 个盒子（编号 n−m+1n−m+1 到编号 nn），然后需要保证 Setsuna 选的前 kk 个盒子里面的巧克力块数之和必须等于 myworld 选的后 mm 个盒子里面的巧克力块数之和 ，即：
编辑
请问，在满足上述要求的前提下，Setsuna 和 myworld 每个人最多可以拿走多少块巧克力？当然，如果选不到符合要求的盒子，那所有巧克力只能被 Wiki 老师独享啦~
输入格式
输入第 11 行包含一个正整数 nn，表示盒子的总数。
输入第 22 行包含 nn 个正整数 aiai，表示每个盒子里面巧克力数量。
输出格式
输出一行，这一行包含一个整数，表示答案。
样例输入1
3 6 3 6
样例输出1
6
样例输入2
4 2 3 1 4
样例输出2
5
样例输入3
5 1 2 3 4 5
样例输出3
0
说明/提示
对于所有测试数据，1≤n≤2×105，1≤ai≤1091≤n≤2×105，1≤ai≤109。、
Java版：
import java.util.Scanner; public class Main { public static void main(String[] args) { // 创建 Scanner 对象用于读取输入 Scanner scanner = new Scanner(System.in); // 读取数组的长度 int n = scanner.nextInt(); // 创建一个长度为 n 的长整型数组 long[] arr = new long[n]; // 循环读取数组的每个元素 for (int i = 0; i < n; i++) { arr[i] = scanner.nextLong(); } // 初始化左指针 int left = 0; // 初始化右指针 int right = n - 1; // 初始化最大相等和为 0 long maxNum = 0; // 初始化左部分的和为左指针指向元素的值 long leftSum = arr[left]; // 初始化右部分的和为右指针指向元素的值 long rightSum = arr[right]; // 双指针循环，只要左指针小于右指针就继续循环 while (left < right) { if (leftSum > rightSum) { // 左部分和大于右部分和，右指针左移 right--; // 更新右部分的和 rightSum += arr[right]; } else if (leftSum < rightSum) { // 左部分和小于右部分和，左指针右移 left++; // 更新左部分的和 leftSum += arr[left]; } else { // 左右部分和相等，更新最大相等和 maxNum = leftSum; // 左指针右移 left++; // 更新左部分的和 leftSum += arr[left]; } } // 输出最大相等和 System.out.println(maxNum); // 关闭 Scanner 对象 scanner.close(); } }
C++版：
#include <iostream> #include <vector> using namespace std; // 当然本题，用双指针就能解决，接下来，我要用双指针解决 int main() { int n; cin>>n; vector<long long> arr(n,0); for(int i=0; i<n; ++i) cin>>arr[i]; int left=0,right=n-1; long long max_num = 0; long long left_sum=arr[left],right_sum=arr[right]; while(left<right){ if(left_sum>right_sum){ right--; right_sum+=arr[right]; }else if(left_sum<right_sum){ left++; left_sum+=arr[left]; }else { max_num = left_sum; left++; left_sum+=arr[left]; } } cout<<max_num<<endl; return 0; }
二、快慢指针：
这个我挺熟悉的，通常是一个指针走得快，另一个走得慢。比如链表问题里，快指针每次走两步，慢指针每次走一步，这样就能用来找链表的中点或者判断是否有环。
题目：环形链表
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回
true。 否则，返回false。示例 1：
编辑
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
编辑
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
编辑
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
提示：
- 链表中节点的数目范围是
[0, 104]-105 <= Node.val <= 105pos为-1或者链表中的一个 有效索引 。
Java版：
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { // 如果头节点为空，说明链表为空，不存在环 if (head == null) return false; // 慢指针，初始指向头节点 ListNode slow = head; // 快指针，初始指向头节点 ListNode fast = head; // 当快指针的下一个节点和下下个节点都不为空时，继续循环 while (fast.next != null && fast.next.next != null) { // 快指针每次移动两步 fast = fast.next.next; // 慢指针每次移动一步 slow = slow.next; // 如果快指针和慢指针相遇，说明链表存在环 if (fast == slow) return true; } // 循环结束，说明没有环 return false; } }
C++版：
/** * 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) return false; ListNode* slow=head; ListNode* fast=head; while(fast->next!=nullptr&&fast->next->next!=nullptr){ fast = fast->next->next; slow = slow->next; if(fast==slow) return true; } return false; } };
三、滑动窗口：
滑动窗口——这个稍微复杂一点，但本质上还是两个指针在操作一个窗口的左右边界。比如在数组中找满足某种条件的最大子数组，滑动窗口可以动态调整窗口的大小，找到最优解。
题目：长度最小的子数组
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于
target的长度最小的 子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
Java版：
class Solution { public int minSubArrayLen(int target, int[] nums) { // 初始化最小子数组长度为 Integer.MAX_VALUE int minNum = Integer.MAX_VALUE; // 滑动窗口的左指针 int left = 0; // 滑动窗口内元素的和 int sum = 0; // 遍历数组，i 作为滑动窗口的右指针 for (int i = 0; i < nums.length; i++) { // 将当前元素加入滑动窗口的和 sum += nums[i]; // 当滑动窗口内元素的和大于等于目标值时 while (sum >= target) { // 更新最小子数组长度 minNum = Math.min(minNum, i - left + 1); // 从滑动窗口的和中减去左指针指向的元素，并将左指针右移 sum -= nums[left++]; } } // 如果最小子数组长度仍然是 Integer.MAX_VALUE，说明没有找到满足条件的子数组，返回 0；否则返回最小子数组长度 return minNum != Integer.MAX_VALUE ? minNum : 0; } }
C++版：
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int min_num = INT32_MAX; int left=0,right; int sum=0; for(int i=0; i<nums.size(); ++i){ // 滑动窗口的右窗口 sum+=nums[i]; while(sum>=target){ min_num = min(min_num,i-left+1); sum-=nums[left++]; } } return min_num!=INT32_MAX ? min_num : 0; } };
四、挑战者系列
题目：日志统计
小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有 NN 行。其中每一行的格式是：
ts idts id
表示在 tsts 时刻编号 idid 的帖子收到一个"赞"。
现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为 DD 的时间段内收到不少于 KK 个赞，小明就认为这个帖子曾是"热帖"。
具体来说，如果存在某个时刻 T 满足该帖在 [T,T+D)[T,T+D) 这段时间内(注意是左闭右开区间)收到不少于 KK 个赞，该帖就曾是"热帖"。
给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。
输入描述
输入格式：
第一行包含三个整数 N,D,KN,D,K。
以下 N 行每行一条日志，包含两个整数 ts 和 id。
其中，1≤K≤N≤105,0≤ts≤105,0≤id≤1051≤K≤N≤105,0≤ts≤105,0≤id≤105。
输出描述
按从小到大的顺序输出热帖 idid。每个 idid 一行。
输入输出样例
示例
输入
7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3
输出
1 3
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
Java版：
import java.util.Arrays; import java.util.Scanner; // 定义结构体 node 对应的类 class Node { int ts; // ts 代表时间 int id; // id 代表序号 // 构造函数，用于初始化 Node 对象 public Node(int ts, int id) { this.ts = ts; this.id = id; } } public class Main { static int n, d, k; static int[] nowlike = new int[100005]; // 用来存放每个 id 帖子的点赞数 static Node[] arr = new Node[100005]; static boolean[] ishot = new boolean[100005]; // 标记每个 id 的帖子是否为热帖 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 从标准输入读取 n, d, k 的值 n = scanner.nextInt(); d = scanner.nextInt(); k = scanner.nextInt(); // 循环读取每条日志的信息 for (int i = 1; i <= n; i++) { int ts = scanner.nextInt(); int id = scanner.nextInt(); arr[i] = new Node(ts, id); } // 对日志数组按照点赞时刻进行排序 Arrays.sort(arr, 1, n + 1, (x, y) -> x.ts - y.ts); int l = 1; // 设置左边界 // 遍历排序后的日志数组 for (int i = 1; i <= n; i++) { // 当前帖子的点赞数加 1 nowlike[arr[i].id]++; // 当当前时刻减去左指针指向的时刻大于等于 d 时，说明超出了长度为 d 的时间段 // 此时需要将左指针指向的帖子的点赞数减 1，并将左指针右移 while (arr[i].ts >= arr[l].ts + d) { nowlike[arr[l].id]--; l++; } // 如果当前帖子在长度为 d 的时间段内的点赞数不少于 k，则将该帖子标记为热帖 if (nowlike[arr[i].id] >= k) { ishot[arr[i].id] = true; } } // 遍历 ishot 数组，输出所有曾经是热帖的帖子编号 for (int i = 0; i < 100005; i++) { if (ishot[i]) { System.out.println(i); } } scanner.close(); } }
C++版：
#include <iostream> #include <algorithm> using namespace std; int n,d,k; int nowlike[100005]; // 用来存放哪一个id数据 struct node{ int ts; // ts代表 时间 int id; // id代表 序号 }; node arr[100005]; bool ishot[100005]; bool cmp(node x,node y) { return x.ts<y.ts; } int main(){ // 妈的，这种错位思想，我一定要学到！！ scanf("%d%d%d",&n,&d,&k); for(int i=1;i<=n;i++) scanf("%d%d",&arr[i].ts,&arr[i].id); sort(arr+1,arr+1+n,cmp); int l = 1; // 设置左边界 for(int i=1; i<=n; ++i) { nowlike[arr[i].id]++; // 帖子+1 while(arr[i].ts>=arr[i].ts+d) { int l_id = arr[l].id; arr[l_id].id--; l++; } if(nowlike[arr[i].id]>=k) ishot[arr[i].id]= true; } for(int i=0; i<100005; ++i){ // 用户id可不这么确定 if(ishot[i]){ cout<<i<<endl; } } return 0; }
借鉴官网、博客：
1、leetcode
2、蓝桥官网
( •̀ ω •́ )✧点击这里，继续学习其他模块吧！
