共计 9035 个字符,预计需要花费 23 分钟才能阅读完成。
数组 + 双指针
数组是一种简单的数据结构,是由相同类型的元素组成的数据集合,并且占据一块连续的内存空间,按照顺序存储数据。
双指针是一种常用的解题思路,可以使用两个相同或相反方向的指针扫描数组从而达到解题目的。
此处的指针非 C/C++里的指针类型,而是一个更加宽泛的概念,它是能够定位数据容器中某个数据的手段。一般是指数组下标。
一、原地修改数组元素题型
原地修改数组的题型一般都需要用到双指针。
LeetCode 26.删除有序数组中的重复项
给定一个有序数组,删除数组中重复元素,确保元素的相对位置不变,并返回删除后的数组长度。
输入:nums = [1,1,2]
输出:2, nums = [1,2]
说明:修改数组后,方法返回修改后的数组长度 2,此时 nums 的长度仍然是 3。但是在进行评测时,只评测返回后的长度大小,超过部分忽略。
思路
首先数组是有序的,意味着如果存在重复元素,那么这些元素就是相邻的,若要删除这些重复元素,就需要将不重复的元素移动左边。
我们声明一个指针left
,该指针始终指向左边非重复项最后一个元素,同时再声明一个指针right
,该指针用于找到和 left 指向的元素不相同的元素。
当left
和right
两个指针指向的元素相同,则让 right 继续向右移动,直到找到不相同的元素。
当left
和right
两个指针指向的元素不同时,先让 left+1,再将当前 left 的元素赋上 right 指向的元素即可。
当right
等于 len 时,非重复项的有序数组长度就是left+1
。
代码
class Solution {
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int len = nums.length;
int l = 0, r=1; // r=0 也行,此时肯定会执行一次r++
while(r < len){
if(nums[l] == nums[r]){
r++;
}else{
l++;
nums[l] = nums[r];
}
}
return l + 1;
}
}
时空复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(1)
LeetCode 27.移除元素
给你一个数组 nums
和一个值 val
,你需要 原地 移除所有数值等于 val
的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1)
额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
输入: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],也会被视作正确答案。
思路
本题和上题一样,原地删除数组中指定元素val
,返回删除后的数组长度,评测时评测返回长度内的元素范围。因此,我们只需要将数组中非val
的值放在左边即可。
声明一个指针left
,该指针始终指向不包含val
的子数组末尾+1;同时再声明一个指针right
,该指针会不断向右找到非val
的值。
当right
指向的元素是val
值时,让 right+1 即可,因为right
指针的目的是找到非val
元素;
当right
指向的元素为非val
值时,将 right 指向的元素赋值到 left 指向的元素上,right 和 left 同时加 1。
当 right 等于 len 时,寻找结束,此时left
就是数组长度。
代码
class Solution {
public int removeElement(int[] nums, int val) {
int len = nums.length;
int left = 0, right = 0;
while(right < len){
// if(nums[right] == val){
// right++;
// }else{
// nums[left] = nums[right];
// left++;
// right++;
// }
// 上述部分可简写成下面的代码
if(nums[right] != val){
nums[left] = nums[right];
left++;
}
right++;
}
return left;
}
}
时空复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(1)
我们可以发现上面两道例题都是通过定1寻1
的方式来完成数组修改的。两个指针中,一个指针负责找到操作位,另外一个指针负责找到操作元素,当无操作元素时,跳出,程序执行完毕。
下面将介绍另外一种齐头并进
的方式,该方式本质上和定1寻1
并无本质区别,只是它们实现的代码会给人一种齐头并进
的感觉.
LeetCode 905.按奇偶排序数组
给你一个整数数组 nums
,将 nums
中的的所有偶数元素移动到数组的前面,后跟所有奇数元素。
返回满足此条件的 任一数组 作为答案。
输入:nums = [3,1,2,4]
输出:[2,4,3,1]
说明:[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。
思路
题目的大概意思就是:给定一个数组,将数组中的偶数放在左边,奇数放在右边。因为题目对空间大小没有要求,因此我们很容易想到一种实现方式:开辟一个同样大小的空数组和两个指针,一个指向头部,另外一个指向尾部,然后遍历数组,依次赋值就行。时空复杂度均为:O(n)
。
那如何只用O(1)
的空间复杂度实现同样的效果呢?很明显我们只能在原数组上进行修改。
因为题目要求偶数在左,奇数在右,因此我们可以声明两个指针left
和right
,让这两个指针分别指向数组的头部和尾部。然后在left < right
的情况下,我们一起移动两指针,直到left
指向奇数元素,right
指向偶数元素,然后交换两指针指向的元素,重复此步骤,就能得到左偶右奇了。
代码
class Solution {
public int[] sortArrayByParity(int[] nums) {
if(nums == null || nums.length == 0) return nums;
int len = nums.length;
int left = 0, right = len - 1;
while(left < right){
// 找到左边为奇数的元素
while(left < len && nums[left]%2==0)left++;
// 找到右边为偶数的元素
while(right > -1 && nums[right]%2==1) right--;
// 交换两个元素
if(left < right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return nums;
}
}
时空复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(1)
LeetCode 922.按奇偶排序数组 II
给定一个非负整数数组 nums
, nums
中一半整数是 奇数 ,一半整数是 偶数 。
对数组进行排序,以便当 nums[i]
为奇数时,i
也是 奇数 ;当 nums[i]
为偶数时, i
也是 偶数 。
你可以返回 任何满足上述条件的数组作为答案 。
输入:nums = [4,2,5,7]
输出:[4,5,2,7]
说明:[4,7,2,5],[2,5,4,7],[2,7,4,5] 也会被接受。
思路
对于非负整数数组,题目要求当下标 i 为奇数时,下标 i 对应的元素 nums[i]也必须时奇数;当 i 为偶数时,nums[i]也是偶数。也就是说对于数组中的每个元素 nums[i],满足:nums[i] % 2 == i % 2
。
如何保证上述条件成立呢?我们只需要定义两个指针p1
和p2
,这两个指针分别指向奇数位
和偶数位
下标,在p1 < len && p2 < len
的情况下,同时移动p1
和p2
指针,当p1
指向偶数,p2
指向奇数时,交换两指针指向的元素,重复上述步骤。
代码
class Solution {
public int[] sortArrayByParityII(int[] nums) {
if(nums == null || nums.length == 0) return nums;
int len = nums.length;
int p1 = 0, p2 = 1; // p1指向偶数,p2指向奇数
while(p1 < len && p2 < len){
// 先找到偶数位为奇数的位置
while(p1 < len && nums[p1] % 2 == p1 % 2) p1 += 2;
// 再找到奇数位为偶数的位置
while(p2 < len && nums[p2] % 2 == p2 % 2) p2 += 2;
// 调换两个位置
if(p1 < len && p2 < len){
int t = nums[p1];
nums[p1] = nums[p2];
nums[p2] = t;
}
}
return nums;
}
}
二、有序数组中的两数之和问题
双指针除了能够让我们对数组进行简单的原地修改外,我们还可以在时空复杂度分别为:O(n)
和O(1)
的情况下找到有序数组中两元素之和等于 target 的元素下标p1
和p2
。
LCR 006. 两数之和 II - 输入有序数组
给定一个已按照 升序排列
的整数数组 numbers
,请你从数组中找出两个数满足相加之和等于目标数 target
。
函数应该以长度为 2
的整数数组的形式返回这两个数的下标值。numbers
的下标 从 0 开始计数 ,所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length
。
假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次。
输入:numbers = [1,2,4,6,10], target = 8
输出:[1,3]
说明:2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
思路
这道题可以通过非常暴力手段进行求解,就是先固定一个数字 nums[i],在从 i 往后依次遍历数组另外一个数字 nums[j],如果nums[i]+nums[j] == k
,则找到了。时空复杂度分别为 O($n^2$)和 O(1)。
除此之外,我们还可以对上面的暴力解法进行优化:固定一个数字 nums[i]后,另外一个数字通过二分查找算法来查找target-nums[i]
。时空复杂度分别为 O($nlogn$)和 O(1)。
另外,我们也可以采用空间换时间手段
将时间复杂度降低至 O(n):创建一个哈希表 map,key 为target-nums[i]
,value 为i
,每次遍历 nums 时,先判断 map 中是否存在target-nums[i]
的值,如果存在,返回:[map.get(target-nums[i]),i],否则向 map 中添加:map.put(nums[i],i)
。时空复杂度均为:O(n),代码如下:
代码
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers == null || numbers.length == 0) return new int[]{-1,-1};
int len = numbers.length;
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<len;i++){
if(map.containsKey(target-numbers[i])){
return new int[]{map.get(target-numbers[i]),i};
}
map.put(numbers[i],i);
}
return new int[]{-1,-1};
}
}
上面的算法仍然没有达到最优的时空效率,我们可以使用双指针的技巧来让时空效率分别达到 O(n)和 O(1)。做法是:定义两个指针 p1 和 p2,分别指向数组头部和尾部,由于数组是有序的,因此当nums[p1]+nums[p2] < target
时,意味着左边小了,因此我们可以让p1+1
;当nums[p1] + nums[p2] > target
时,意味着右边大了,因此我们可以让p2-1
,如此往复,直到两指针相遇退出或两指针指向的元素之和等于 targte 时,返回[p1,p2]。
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers == null || numbers.length == 0) return new int[]{-1,-1};
int len = numbers.length;
int p1 = 0, p2 = len - 1;
while(p1 < p2){
int sum = numbers[p1] + numbers[p2];
if(sum > target){
p2--;
}else if(sum < target){
p1++;
}else{
return new int[]{p1,p2};
}
}
return new int[]{-1,-1};
}
}
LeetCode 35.三数之和
本题可视为是两数之和的进阶。
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
说明:
- nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
- nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
- nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
- 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
- 注意,输出的顺序和三元组的顺序并不重要。
思路
这道题对于会两数之和的人来说非常简单,三个数字,我们确定一个nums[i]
,然后在[i,n-1]的区间里寻找两数之和等于-nums[i]
,如果存在这两个数,说明找到了一个三元组。现在需要解决的是,如何对三元组进行去重,这其实也很简单。当找到一个三元组[nums[i],nums[j],nums[k]]时,跳过所有相同的值就能过滤掉重复的三元组,这也就意味着,我们需要对数组进行排序,因为只有排序后的数组,相同元素彼此相邻。
代码
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if(nums == null || nums.length == 0) return new LinkedList<>();
int len = nums.length;
List<List<Integer>> result = new LinkedList<>();
Arrays.sort(nums);
// 先固定nums[i],然后在[i+1,n-1]的区间里找到两数之和等于-nums[i]的下标
for(int i=0; i<len-2;){
twoSum(nums, i, result);
int temp = nums[i];
// 跳过nums[i]的重复值
while(i<len&&nums[i] == temp) i++;
}
return result;
}
// 求解两数之和
private void twoSum(int[] nums, int i, List<List<Integer>> result){
int len = nums.length;
int left = i+1, right = len - 1;
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if(sum == 0){
result.add(List.of(nums[i],nums[left],nums[right]));
int temp = nums[left];
while(left < len && nums[left] == temp) left++;
}else if(sum > 0){
right--;
}else{
left++;
}
}
}
}
三、无序数组的子数组问题
上面主要讨论了在有序数组中,使用双指针可以在 O(n)和 O(1)的时空复杂度下求解数组中两元素之和等于 target 的两元素下标,那么在无序数组中,双指针又能干嘛呢?
无序数组中双指针的经典运用就是滑动窗口。我们使用两个指针p1
和p2
维护着数组中的一段子区间,这就构成了一个窗口。通过移动两指针,保证该窗口内的元素满足某个特性,当移动到末尾时,程序结束得到结果。
LeetCode 643.子数组最大平均数 I
给你一个由 n
个元素组成的整数数组 nums
和一个整数 k
。
请你找出平均数最大且 长度为 k
的连续子数组,并输出该最大平均数。
任何误差小于 $10^{-5}$ 的答案都将被视为正确答案。
输入:nums = [1,12,-5,-6,50,3], k = 4
输出:12.75
解释:最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
思路
本题可以简单表述为:求给定数组的指定长度 k 的子数组最大平均数。需要注意的是:最大平均数 = 最大元素之和 / k。因此本题本质上是让我们求指定长度 k 的最大元素之和。因此,我们可以使用滑动窗口
手段,使用两指针p1
和p2
,这两个指针共同构成了一个窗口。
移动 p2,当p2 - p1 + 1 == k
时,说明窗口长度为 k,此时计算窗口内的所有元素之和。计算元素之和我们不需要通过遍历,只需要定义一个变量sum
,当 p2 元素滑入窗口时,sum += nums[p2]
即可,当 p1 元素滑出窗口时,sum -= nums[p1]
,这样 sum 就始终是窗口内元素之和了。
当窗口长度为 k,并计算出元素之和后,我们就能求解最大元素之和maxSum
,同时,p1 ++;
,让 p1 所在元素滑出窗口。
当 p2 到达末尾时,程序结束,我们就能得到最大子数组元素之和 maxSum 了,返回时,返回maxSum / k * 1.0
即可。
代码
class Solution {
public double findMaxAverage(int[] nums, int k) {
if(nums == null || nums.length == 0 || nums.length < k) return 0;
int len = nums.length, p1 = 0, maxSum = Integer.MIN_VALUE, sum = 0;
for(int p2 = 0; p2 < len; p2 ++){
sum += nums[p2];
// 当窗口长度为k
if(p2 - p1 + 1 == k){
// 计算最大和
maxSum = Math.max(sum, maxSum);
// p1所在元素滑出
sum -= nums[p1++];
}
}
return maxSum / (k * 1.0);
}
}
上述入门例题告诉我们设计一个滑动窗口我们需要考虑以下几点:
- 右边元素(p2 指针)什么条件下滑入?
- 左边元素(p1 指针)什么条件下滑出?
- 窗口内的所有元素能带给我们什么性质?
带着上面三个问题,我们不妨再试试下面的例题
LeetCode 713.乘积小于 K 的子数组
给你一个整数数组 nums
和一个整数 k
,请你返回子数组内所有元素的乘积严格小于 k
的连续子数组的数目。
输入:nums = [10,5,2,6], k = 100
输出:8
解释:8 个乘积小于 100 的子数组分别为:[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
思路
本题的求解方向非常明确,让我们求解子数组乘积小于 k 的数量。现在假设一段子数组[p1,p2]
内的元素之积小于 k,那么[p1,p2]
内乘积小于 k 的子数组数量有多少呢?
对于乘积小于 k 的子数组[p1,p2]
,p2 是固定不动的,因此[p1+1,p2]
,[p1+2,p2]
,...,[p1 + n, p2]
均是小于 k 的子数组,而个数就是p2 - p1 + 1
。因此,每当我们找到乘积小于 k 的子数组[p1,p2]
时,将p2-p1+1
进行累加即可求出子数组之和。
代码
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if(nums == null || nums.length == 0) return 0;
int p1 = 0, len = nums.length, mul = 1,res = 0;
for(int p2 = 0; p2 < len; p2++){
mul *= nums[p2];
// 滑出条件:窗口内的元素之积>=k时
while(p1 <= p2 && mul >= k){
mul /= nums[p1++];
}
// 此时窗口内的元素之积一定小于k
res += p2 - p1 + 1;
}
return res;
}
}
LeetCode 2461.长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和:
- 子数组的长度是 k,且
- 子数组中的所有元素 各不相同 。
- 返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件,返回 0 。
思路
本题给我们的滑动窗口添加了一个限制:元素不能重复。我们首先想到使用用哈希表,因为哈希表本身就具有去重功能,因此,我们将滑动窗口里的元素放在哈希表中即可。
代码
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
if(nums == null || nums.length == 0 || nums.length < k) return 0;
int p1 = 0, len = nums.length;
long ans=0, sum = 0;
Set<Integer> set = new HashSet<>();
for(int p2 = 0;p2<len;p2++){
// 如果滑入的元素p1已经存在了,那么将p1元素移出,直到set中不存在p2元素
while(set.contains(nums[p2])){
set.remove(nums[p1]);
sum -= nums[p1++];
}
// sum是窗口中元素的和
sum += nums[p2];
set.add(nums[p2]);
// 当长度为k时,计算最大和
if(p2 - p1 + 1 == k){
ans = Math.max(ans, sum);
sum -= nums[p1];
set.remove(nums[p1++]);
}
}
return ans;
}
}
总结
- 原地修改数组元素;
- 数组有序,找两数之和问题;
- 数组无序,元素均是正数,可求解具有某个性质的子数组;