滑动窗口法

Sliding Window

目的：减少while循环

引例：

对于数组a = [1, 4, 2, 3, 4, 5, 6]，3个元素一组，找出最大的和

• 容易想到利用循环解决这道题，但是一旦元素个数增加，循环次数也会随之急剧增加

滑动窗口法

• 定义两个指针left、right，他们之间构成一个窗口
• 计算出窗口内元素的和

• left与right指针右移，可以观察到，其中有部分元素是重复的，因此只需要减去旧元素，加上新元素即可

public class SlidingWindowAlgorithm {

public static void main(String[] args) {

int[] nums = {1, 4, 2, 3, 4, 5, 6};

int maxSum = 0;

int localSum = 0;

int windowWidth = 3; // 窗口宽度

int left = 0;

int right = left + windowWidth - 1;

while (right < nums.length) {

if (left == 0) { // 第一个窗口

for (int i = left; i <= right; i++)

localSum += nums[i];

} else { // 之后的窗口，滑动

localSum = localSum - nums[left - 1] + nums[right];

}

if (localSum > maxSum) maxSum = localSum;

left++;

right++;

}

System.out.println("max sum = " + maxSum);

}

}

Leetcode题目

• 209.长度最小的子数组
• 3.无重复字符的最长子串
• 424.替换后的最长重复字符