请分别给出一个快慢指针和滑动窗口的java代码示例
时间: 2024-04-10 14:34:04 浏览: 106
快慢指针的实现
下面是一个快慢指针的 Java 代码示例,用于寻找链表的中间节点:
```java
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // 慢指针每次移动一步
fast = fast.next.next; // 快指针每次移动两步
}
return slow; // 返回中间节点
}
```
在该代码中,我们使用了快慢两个指针 `slow` 和 `fast`,它们都从链表的头部开始移动。慢指针 `slow` 每次移动一步,而快指针 `fast` 每次移动两步。通过这种方式,当快指针 `fast` 到达链表末尾时,慢指针 `slow` 正好到达链表的中间位置。
下面是一个滑动窗口的 Java 代码示例,用于在数组中找到和大于等于给定目标值的最短子数组长度:
```java
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int right = 0;
int sum = 0;
int minLen = Integer.MAX_VALUE;
while (right < nums.length) {
sum += nums[right]; // 右指针向右移动,并累加元素值
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1); // 更新最小长度
sum -= nums[left]; // 左指针向右移动,并减去元素值
left++; // 缩小窗口大小
}
right++; // 扩大窗口大小
}
return minLen == Integer.MAX_VALUE ? 0 : minLen; // 返回最短子数组长度
}
```
在该代码中,我们使用了两个指针 `left` 和 `right` 来构成一个窗口,窗口的右边界由 `right` 控制。通过调整窗口的大小和位置,我们不断计算窗口内元素的和 `sum`,并与目标值进行比较。如果 `sum` 大于等于目标值,我们将左指针 `left` 向右移动,并减去窗口左侧的元素值,直到 `sum` 小于目标值。在此过程中,我们记录并更新窗口大小的最小值 `minLen`。最后返回最小值作为结果。
需要注意的是,滑动窗口算法适用于解决一些需要寻找满足特定条件的子数组或子串的问题,可以通过调整窗口大小和位置来逐步逼近目标值。具体问题中可能会有一些边界条件和特殊情况需要处理。以上代码示例仅供参考,实际应用中需要根据具体情况进行调整。
阅读全文