• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

# LC算法技巧总结（二）：双指针和滑动窗口技巧

1周前 (09-11) 13次浏览

## 一、快慢指针的常见算法

1、判定链表中是否含有环

``````boolean hasCycle(ListNode head) {
return false;
}
``````

``````boolean hasCycle(ListNode head) {
ListNode fast, slow;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;

if (fast == slow) return true;
}
return false;
}
``````

2、已知链表中含有环，返回这个环的起始位置

``````ListNode detectCycle(ListNode head) {
ListNode fast, slow;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
``````

3、寻找链表的中点

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

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

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

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

## 二、左右指针的常用算法

1、二分查找

``````int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
``````

2、两数之和

``````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];Java
nums[right] = temp;
left++; right--;
}
}
``````

4、滑动窗口算法

## 三、滑动窗口技巧

``````int left = 0, right = 0;

while (right < s.size()) {`
// 增大窗口
right++;

while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
``````

``````/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;

int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...

/*** debug 输出的位置 ***/
printf("window: [%d, %d)n", left, right);
/********************/

// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
``````