Leetcode | 双指针系列

题名 难度 题解
167.两数之和 II - 输入有序数组 简单
26.删除排序数组中的重复项 简单
977.有序数组的平方 简单
15.三数之和 中等
16.最接近的三数之和 中等
923.三数之和的多种可能 中等
713.乘积小于K的子数组 中等
75.颜色分类 中等
18.四数之和 中等
844.比较含退格的字符串 简单
11.盛最多水的容器 中等

167.两数之和 II - 输入有序数组

题目:
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

思路:

使用双指针,左指针指向第一个元素,右指针指向最后一个元素

  • 如果两个指针指向元素的和sum==target,那么得到要求的结果;
  • 如果sum<target,移动较小的元素,使 sumsum 变大一些。
  • 如果sum>target,移动较大的元素,使sum变小一些;

复杂度:

数组中的元素最多遍历一次,时间复杂度为 O(N)。只使用了两个额外变量,空间复杂度为 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0;
int right = numbers.size()-1;
while(left<right){
int two_sum = numbers[left] + numbers[right];
if (two_sum==target){
return {left+1,right+1};
}else if(two_sum<target){
left++;
}else{
right--;
}
}
return {};
}
};

此题中双指针往中间移动时,为何不会漏掉某种情况?一张图解释:

26.删除排序数组中的重复项

题目:
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

思路:

  • 使用两个指针 i 和 j,其中 j 是慢指针,而 i 是快指针。
  • 只要nums[i]=nums[j],我们就增加i以跳过重复项。
  • 当nums[j] = nums[i] 时,把nums[i]的值复制到nums[j]。然后递增 j,重复相同过程,直到 i 到达数组的末尾为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()==0){
return 0;
}
int j = 0;
for(int i=0;i<nums.size();i++){
if(nums[i]!=nums[j]){
j++;
nums[j] = nums[i];
}

}
return j+1;
}
};

977.有序数组的平方

题目:
https://leetcode-cn.com/problems/squares-of-a-sorted-array/

思路:

数组有序, 负数平方之后会有可能成为最大数。那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。此时可以考虑双指针法了,i指向起始位置,j指向终止位置。

  • 定义一个新数组res,和A数组一样的大小,让k指向result数组终止位置。
  • 如果A[i] * A[i] < A[j] * A[j] 那么res[k–] = A[j] * A[j]; 。
  • 如果A[i] * A[i] >= A[j] * A[j] 那么res[k–] = A[i] * A[i]; 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> sortedSquares(vector<int>& A) {
int left = 0, right = A.size()-1;
vector<int> res(A.size(),0);
int k = A.size()-1;
for(int i=left,j=right;i<=j;){
if(A[i]*A[i]<=A[j]*A[j]){
res[k--] = A[j]*A[j];
j--;
}else{
res[k--] = A[i]*A[i];
i++;
}
}
return res;
}
};

15.三数之和

题目:
https://leetcode-cn.com/problems/3sum/

思路:

  • 固定 3 个指针中最左(最小)数字的指针 i,双指针 left,right 分设在数组索引 (i,nums.size()) 两端,通过双指针交替向中间移动,记录对于每个固定指针 i 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 left,right 组合:
  • 当 nums[i] > 0 时直接break跳出:因为 nums[left] >= nums[right] >= nums[i] > 0,即 3 个数字都大于 0 ,在此固定指针 i 之后不可能再找到结果了。
  • 当 i > 0且nums[i] == nums[i - 1]时即跳过此元素nums[i]:因为已经将 nums[i - 1] 的所有组合加入到结果中,本次双指针搜索只会得到重复组合。
  • left,right 分设在数组索引 (i, nums.size())两端,当left < right时循环计算sum = nums[i] + nums[left] + nums[right],并按照以下规则执行双指针移动:
    • 当s < 0时,left += 1并跳过所有重复的nums[left];
    • 当s > 0时,right -= 1并跳过所有重复的nums[right];
    • 当s == 0时,记录组合[nums[i], nums[left], nums[right]]至res,执行left += 1和right -= 1并跳过所有重复的nums[left]和nums[right],防止记录到重复组合。
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
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int target;
vector<vector<int>> res;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(i>0 && nums[i]==nums[i-1]) continue;
if((target=nums[i])>0) break;
int left = i+1,right = nums.size()-1;
while(left < right){
int sum = nums[i]+nums[left]+nums[right];
if(sum>0){
--right;
}else if(sum<0){
++left;
}else{
res.push_back({nums[i],nums[left],nums[right]});
++left;
--right;
while(left< right && nums[left]== nums[left-1]) ++left;
while(left< right && nums[right] == nums[right+1]) --right;
}
}
}
return res;
}
};

713.乘积小于K的子数组

题目:
https://leetcode-cn.com/problems/subarray-product-less-than-k/

思路:

  • 当k<=1时,由于数组为正整数数组,明显不存在满足题意的连续子数组,故直接返回结果0。
  • 令保存结果的变量res=0,滑动区间左指针left=0,保存滑动区间中元素乘积的变量pro为1。
  • 令右指针right从数组左到右滑动,每滑动1次,让pro乘以新元素。如果此时pro大于等于k,则滑动左指针left,每滑动一次令pro除以nums[left],得到新的滑动区间的元素乘积,直到pro<k。此时,以right为右边界,以滑动区间中任一元素为左边界的子数组都满足题意。由此可以得到以right为子数组右边界的所有子树组的个数right-left+1,将改数值累加至结果res。
  • 当right滑动到最右端后,res中便累加了以各个元素为子数组右端点时的有效子数组个数。返回res即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k <= 1){
return 0;
}
int left = 0, right = 0;
int pro = 1;
int res = 0;
while(right < nums.size()){
pro *= nums[right];
while(pro >= k){
pro /= nums[left];
left++;
}
res+= right - left + 1 ;
right++;
}
return res;
}
};

844. 比较含退格的字符串

题目:

https://leetcode-cn.com/problems/backspace-string-compare/

思路:

用栈处理遍历过程,每次我们遍历到一个字符:

  • 如果它是退格符#,那么我们将栈顶字符弹出;
  • 如果它是普通字符,那么我们将其压入栈中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
string Build(string str){
string s;
for(char t:str){
if(t!='#'){
s.push_back(t);
}else if(!s.empty()){
s.pop_back();
}
}
return s;
}
bool backspaceCompare(string S, string T) {
return Build(S)==Build(T);
}
};
分享到