滑动窗口和双指针I

发表于 分类于 本文字数： 10k 阅读时长 ≈ 9 分钟

滑动窗口与双指针 I

「滑动窗口」和「双指针」，其实「滑动窗口」也可以称为「双指针」，在这个专题里会着重介绍这两类题型的思考路径。

引入

循环不变量

循环不变量」是指我们在编写代码的过程中，要一直循序不变的性质，这样的性质是根据要解决的问题，由我们自己定义的。「循环不变量」是我们写对一个问题的基础，保证了在「初始化」「循环遍历」「结束」这三个阶段相同的性质，使得一个问题能够被正确解决。

例题：

  • 删除有序数组中的重复项
    给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

1
2
3
4
5
示例：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后

思路：
给出两种写法，两种写法里 i 都是用于遍历的下标，而 j 的含义不同，
定义1：j 指向马上要赋值的元素的下标，因此我们定义区间 [0..j) （注意是左闭右开区间，j 不能取到）里没有重复元素。pre 永远指向第 1 个不重复的数字；

  • 初始化：为了保证区间 [0..j) （注意这里是左闭右开区间）里没有重复元素。初始的时候，i = 0 ，下标为 0 的位置只有一个数，区间 [0..j) 一定不会出现重复，这件事情表示为区间 [0..0] 没有重复数字，即区间 [0..1) 没有重复数字，因此 j 初始化的时候需要等于 1；
  • 保持：遇到和 pre 指向的数字相等元素，i++ 直接看到下一个元素，如果 nums[i] != pre ，表示程序看到了第 1 个不重复的数字，此时需要赋值 nums[j] = nums[i] 和 pre = nums[j] ，然后让 j++ 指向下一个需要赋值的下标；
  • 终止：循环结束以后 i = len ，程序看完了输入数组的所有元素，此时区间 [0..j) 里没有重复元素，它的长度为 j ，返回 j。
  1. 参考代码1:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public class Solution {

        public int removeDuplicates(int[] nums) {
     		int len = nums.length;
     		if(len<2){
     			return len ;
     		}
     		int j=1;
     		int pre = nums[0];
        	for(int i=1; i < len;i++){
        		if(nums[i]!=pre){
        			nums[j] = nums[i];
        			pre = nums[j];
        			j++;
        		}
        	}
        	return j;
        }
     }

定义2 ： 我们定义：区间 [0..j] （注意这里是左闭右闭区间）没有出现重复元素，此时变量 j 是上一轮找到的第 1 次出现的元素的下标。因此我们不需要像「定义 1」一样给 pre 定义。循环变量 i 看到的数值 nums[i] 永远和变量 j 看到的数值 nums[j] 进行比较。 大家可以对照上面的「定义 1」自行写出「初始化」「保持」「终止」的逻辑。

  1. 参考代码2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {

    public int removeDuplicates(int[] nums) {
    	int len = nums.length;
    	if(len<2){
    		return len;
    	}
    	int j=0;
    	for(int i=1;i<len;i++){
    		if(nums[i] != nums[j]){
    			j++;
    			nums[j]=nums[i];
    		}
    	}
    	return j+1;
    }
}
  • 最长连续递增序列
    给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
    连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
    1
    2
    3
    4
    5
    6
    示例：
    输入：nums = [1,3,5,4,7]
    输出：3
    解释：最长连续递增序列是 [1,3,5], 长度为3。
    尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

思路：
题目要求我们找的子序列是连续的，并且子序列里的元素要求 严格单调递增。在遍历的时候，从第 2 个元素开始；

如果当前遍历到的元素比它左边的那一个元素要严格大，「连续递增」的长度就加 11；
否则「连续递增」的起始位置就需要重新开始计算。

参考代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {

    public int findLengthOfLCIS(int[] nums) {
    	int len = nums.length;
    	int res = 0;
    	int i = 0;
    	int j = 0;
    	while(j<len){
    		if(j>0 && nums[j-1]>=nums[j]){
    			i = j;
    		}
    		j++;
    		res = Math.max(res,j-i) ;
    	}
    	return res ;
    }
}

参考代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {

    public int findLengthOfLCIS(int[] nums) {
    	int len = nums.length ;
    	int res = 0;
    	int i = 0;
    	int j =0 ;
    	while(j<len){
    		if(j>0 && nums[j-1]>=nums[j]){
    			i = j;
    		}
    		res = Math.max(res , j-i+1);
    		j++;
    	}
    	return res;
    }
}

扩展练习

  • 移除元素
    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
1
2
3
4
5
示例：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int removeElement(int[] nums, int val) {
    	int n = nums.length;
    	int l = 0;
    	for(int r= 0;r<n ;r++){
    		if(nums[r] ! =val){
    			nums[l] = nums[r];
    			l++;
    		}
    	}
    	return l;
    }
}

优化之后的代码

我们依然使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。
算法： 如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。
当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int removeElement(int[] nums, int val) {
    	int left = 0;
    	int right = nums.length;
    	while(left < right){
    		if(nums[left] == val){
    			nums[left] = nums[right-1];
    			right--;
    		}else{
    			left++
    		}
    		return left;
    	}
    }
}
  • 删除排序数组中的重复项 II

    给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
    不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

1
2
3
4
5
示例：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

思路：
因为给定数组是有序的，所以相同元素必然连续。我们可以使用双指针解决本题，遍历数组检查每一个元素是否应该被保留，如果应该被保留，就将其移动到指定位置。具体地，我们定义两个指针 slow 和 fast 分别为慢指针和快指针，其中慢指针表示处理出的数组的长度，快指针表示已经检查过的数组的长度，即 nums[fast] 表示待检查的第一个元素，nums[slow−1] 为上一个应该被保留的元素所移动到的指定位置。

因为本题要求相同元素最多出现两次而非一次，所以我们需要检查上上个应该被保留的元素 \textit{nums}[\textit{slow} - 2] 是否和当前待检查元素 \textit{nums}[\textit{fast}] 相同。当且仅当 \textit{nums}[\textit{slow} - 2] = \textit{nums}[\textit{fast}] 时，当前待检查元素 \textit{nums}[\textit{fast}]nums[fast] 不应该被保留（因为此时必然有 \textit{nums}[\textit{slow} - 2] = nums[\textit{slow} - 1] = \textit{nums}[\textit{fast}]。最后，\textit{slow} 即为处理好的数组的长度。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int removeDuplicates(int[] nums) {
    	int n = nums.length;
    	if(n<=2){
    		return n;
    	}
    	int slow = 2 ,fast = 2;
    	while(fast < n){
    		if(nums[slow-2] != nums[fast]){
    			nums[slow] = nums[fast];
    			++slow;
    		}
    		++fast;
    	}
    	return fast;
    }
}

或者：

class Solution {
    public int removeDuplicates(int[] nums) {
    	return process(nums,2);
    }
    int process(int[] nums , int k){
    	int u =0;
    	for(int x:nums){
    		if(u<k || nums[u-k] != x)  nums[u++]=x;
    	}
    	return u;
    }
}
  • 移动零

    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    请注意，必须在不复制数组的情况下原地对数组进行操作。

    1
    2
    3
    示例：
    输入: nums = [0,1,0,3,12]
    输出: [1,3,12,0,0]

思路：
使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
注意：

  1. 左指针左边均为非零数
  2. 右指针左边至左指针均为零

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution{
	public void moveZeroes(int[] nums){
		int n = nums.length , left = 0,right = 0;
		while(right < n){
			if(nums[right]! = 0){
				swap(nums, left ,right);
				left++;
			}
			right++;
		}
	}
	public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

使用循环不变量写对代码

我们在写代码的时候一定要明确自己对变量以及区间的定义是什么，并且在编写代码的过程中保持定义不变。

例题

  • 颜色分类

    给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
    此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

1
2
3
示例：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

思路：
可以在区间上设置两个表示分界的位置，并且定义循环不变量；

  • 所有元素在区间【0···Zero】= 0;
  • 所有元素在区间【zero···i】= 1;
  • 区间 [i..two) 是程序没有看到的部分；
  • 所有的元素在区间 [two..len - 1] = 2，这里 len 表示数组的长度。

为了让初始化的时候三个区间都为空区间，zero = 0，two = len，程序没有看到的部分是整个数组。程序什么时候终止呢？当 i == two 时，三个子区间正好覆盖了整个数组，程序没有看到的部分为空，因此循环可以继续的条件是：i < two 。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {

    public void sortColors(int[] nums) {
    	int len = nums.length;
    	if(len<2) return ;

    	int zero = 0 ;
    	int two = len;
    	int i = 0;
    	while(i<len){
    		if(nums[i] == 0){
    			swap(nums,i,zero);
    			i++;
    			zero++;
    		}else if(nums[i] == 1){
    			i++;
    		}else{
    			two -- ;
    			swap(nums,i,two);
    			swap
    		}
    	}
    }
}
  • 数组中的第 K 个最大元素

    在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

    1
    2
    3
    4
    示例：
    输入: [3,2,1,5,6,4] 和 k = 2
    输出: 5

    思路：
    这道题可以使用优先队列（堆）完成。我们这里展示另一种使用快速排序 partition 的知识解决的办法。我们给出三种循环不变量的定义。

循环不变量定义 1： 把等于切分元素的所有元素分到了数组的同一侧。
我们定义 pivot = nums[left] ，剩下的区间 [left + 1..right] 被变量 le 分成三个部分：

  1. [left + 1 .. le] <= pivot；
  2. (le..i] > pivot；
  3. (i..right] 是程序没有看到的部分。

参考代码1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
    	int len = nums.length;
    	 // 第 k 大元素的下标是 len - k
    	int target = len - k;
    	int left = 0 ;
    	int right = len-1;
    	while(true){
    		int pIndex = partition(nums,left,right);
    		if(pIndex == target) {
    			return nums[pIndex];
    		} else if( pIndex < target){
    			// 下一轮搜索区间 [pIndex + 1..right]
    			left = pIndex + 1;
    		} else{
    			// pIndex > target
                // 下一轮搜索区间 [left..pIndex - 1]
                right = pIndex - 1;
    		}
    	}
    }
    private int partition(int[] nums, int left,int right){
    	int ranndomIndex = left +random.nextInt(right - left + 1);
    	swap(nums, left ,randomIndex);

    	int pivot = nums[left];
    	// [left + 1 .. le] <= pivot
        // (le..i] > pivot
        // 注意：一定要设置成 left ，否则交换会出错

        int le = left ;
        for(int i = left+1 ;i <=right ;i++){
        	// 这里写 < 或者 <= 都可以
        	if(nums[i]<=pivot){
        		left++;
        		swap(nums,le,i);
        	}
        }
        swap(nums,left,le);
        return le;
    }
}

循环不变量定义 2 ： 把等于切分元素的所有元素 等概率 地分到了数组的两侧，避免了递归树倾斜，递归树相对平衡。
我们定义 pivot = nums[left] ，剩下的区间 [left + 1..right] 被变量 le 、ge 分成三个部分：

  1. [left..le) <= pivot；
  2. [le..ge] 是程序没有看到的部分；
  3. (ge..right] >= pivot。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
    	int len = nums.length ;
    	int left = 0;
    	int right = len -1 ;

    	// 第k个元素的下标是 len - k;
    	int target = len - k;
    	while(true) {
    		int index = partition(nums,left,right);
    		if(index == target){
    			return nums[index];
    		}else if(index < target){
    			left = index + 1;
    		}else{
    			right = index - 1;
    		}
    	}
    }
    public int partition(int[] nums ,int left , int right){
    	// 在区间随机选择一个元素作为标定点
        int randomIndex = left + random.nextInt(right - left + 1 );
        swap(nums, left, randomIndex);

        int pivot = nums[left];

        // 将等于 pivot 的元素分散到两边
        // [left..le) <= pivot
        // (ge..right] >= pivot

        int le = left + 1;
        int ge = right;

        while(true){
        	// 遇到 nums[le] >= pivot 的时候停下来
            // 遇到与 pivot 相等的元素，是通过交换被等概率分到两边的
            while(le <= ge && nums[le] < pivot){
            	le++;
            }
            while(le <= ge && nums[ge] > pivot){
            	ge--;
            }

            if(le > ge){
            	break;
            }
            swap(nums,le,ge);
            le++;
            ge--;
        }
        swap(nums,left,ge);
        return ge ;
    }
}

循环不变量定义 3： 把等于切分元素的所有元素挤到了数组的中间，在有很多元素和切分元素相等的情况下，递归区间大大减少。
我们定义 pivot = nums[left] ，剩下的区间 [left + 1..right] 被变量 lt 、gt 分成四个部分：

  1. [left + 1..lt] < pivot；
  2. [lt + 1..i) = pivot ；
  3. [i..gt) 是程序没有看到的部分；
  4. [gt..right] > pivot。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class Solution {

    private static Random random = new Random(System.currentTimeMillis());

    public int findKthLargest(int[] nums, int k) {
   		int len = nums.length ;
   		int target = len - k;

   		int left = 0;
   		int right = len - 1;
   		while(true){
   			int[] pIndex = partition(nums,left,right);

   			int index1 = pIndex[0];
   			int index2 = pIndex[1];

   			if(target < index1){
   				// 下一轮搜索区间 [left..index1 - 1]
                right = index1 - 1;
   			}else if(target == index1){
   				return nums[index1];
   			}else if(target < index2){
   				left = index1 + 1;
   				right = index2 - 1;
   			}else if(target == index2){
   				return nums[index2];
   			}else{
   				// pIndex > target
                // 下一轮搜索区间 [index2 + 1..right]
                left = index2 + 1;
   			}
   		}
    }
    private int[] partition(int[] nums, int left, int right) {
        int randomIndex = left + RANDOM.nextInt(right - left + 1);
        swap(nums, randomIndex, left);

		// 循环不变量：
        // all in [left + 1..lt] < pivot
        // all in [lt + 1..i) = pivot
        // all in [gt..right] > pivot

        int pivot = nums[left];
        int lt = left;
        int gt = right + 1;

        int i = left+1;
        while(i < gt){
        	if (nums[i] < pivot) {
                lt++;
                swap(nums, i, lt);
                i++;
            } else if (nums[i] == pivot) {
                i++;
            } else {
                gt--;
                swap(nums, i, gt);
            }
        }
        swap(nums,left,lt);
        return new int[]{lt,gt-1};
	}
}

-------------本文结束感谢您的阅读-------------
作者水平有限，文中难免存在一些错误，欢迎邮件@交流讨论~
Zongpeng Lin 微信 微信
Zongpeng Lin 支付宝 支付宝