前言
双指针算法入门,干就完了
下面的题目都是来自灵神的基础算法精讲,有思路不清晰的地方,可以去看讲解。
灵茶山艾府的个人空间-灵茶山艾府个人主页-哔哩哔哩视频 (bilibili.com)
相向双指针
1.两数之和
题目链接:167. 两数之和 II - 输入有序数组 - 力扣(LeetCode)
题目描述
给你一个下标从 1 开始的整数数组 numbers
,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target
的两个数。如果设这两个数分别是 numbers[index1]
和 numbers[index2]
,则 1 <= index1 < index2 <= numbers.length
。
以长度为 2 的整数数组 [index1, index2]
的形式返回这两个整数的下标 index1
和 index2
。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1:
输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:
输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3:
输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
提示:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers
按 非递减顺序 排列-1000 <= target <= 1000
- 仅存在一个有效答案
代码
C++
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
int left = 0;
int right = n - 1;
while (left < right) {
int s = numbers[left] + numbers[right];
if (s == target) {
break;
} else if (s > target) {
right -= 1;
} else {
left += 1;
}
}
return {left + 1, right + 1};
}
};
Java
class Solution {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
int[] res = new int[2]; // 定义数组,用于最终答案的存储
int left = 0;
int right = n - 1;
while (left < right) {
int s = numbers[left] + numbers[right];
if (s == target) {
res[0] = left + 1;
res[1] = right + 1;
break;
} else if (s > target) {
right -= 1;
} else {
left += 1;
}
}
return res;
}
}
2.三数之和
题目链接:15. 三数之和 - 力扣(LeetCode)
题目描述
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请
你返回所有和为 0
且不重复的三元组。
**注意:**答案中不可以包含重复的三元组。
示例 1:
输入: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] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
提示:
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
代码
C++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 对nums数组排序
vector<vector<int>> ans; // 最终结果
int n = nums.size(); // nums数组的长度
for (int i = 0; i < n - 2; i++) { // i < n - 2是要给left、right留下位置
int x = nums[i];
if (i && x == nums[i - 1])
continue; // 跳过重复数字
if (x + nums[i] + nums[i + 1] > 0)
break; // 因为nums是排好序的,数组的前三个数相加都大于0了,那么后面的数字相加不可能等于0
if (x + nums[n - 1] + nums[n - 2] < 0)
continue; // 如果当前的x与最大的两个数相加小于0,那么x与中间的任意数字相加都小于0,直接可以枚举下一个x了。
int left = i + 1;
int right = n - 1;
while (left < right) {
int s = x + nums[left] + nums[right]; // 先计算出三者相加的结果
if (s > 0)
right--; // s > 0的话,代表右边的数大了,所以右指针左移
else if (s < 0)
left++; // s < 0的话,代表左边的数小了,所以左指针右移
else {
ans.push_back({x, nums[left], nums[right]});
left++;
while (left < right &&
nums[left] == nums[left - 1]) { // 跳过重复数字
left++;
}
right--;
while (right > left &&
nums[right] == nums[right + 1]) { // 跳过重复数字
right--;
}
}
}
}
return ans;
}
};
Java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 数组排序
List<List<Integer>> ans = new ArrayList<>(); // 最终结果
int n = nums.length; // 数组长度
for (int i = 0; i < n - 2; i++) { // 遍历数组,留出位置给左右指针
int x = nums[i];
if (i > 0 && x == nums[i - 1])
continue; // 跳过重复数字
if (x + nums[i + 1] + nums[i + 2] > 0)
break; // 如果前三个数相加已经大于0,后面的数字相加不可能等于0
if (x + nums[n - 1] + nums[n - 2] < 0)
continue; // 如果当前数字与最大的两个数字相加小于0,直接枚举下一个数字
int left = i + 1;
int right = n - 1;
while(left < right){
int s = x + nums[left] + nums[right];
if(s > 0) right--; // 右指针左移
else if(s < 0) left++; // 左指针右移
else{
ans.add(List.of(x,nums[left],nums[right]));
left++;
while (left < right && nums[left] == nums[left - 1]) {
left++; // 跳过重复数字
}
right--;
while (right > left && nums[right] == nums[right + 1]) {
right--; // 跳过重复数字
}
}
}
}
return ans;
}
}
3.最接近的三数之和
题目链接:16. 最接近的三数之和 - 力扣(LeetCode)
题目描述
给你一个长度为 n
的整数数组 nums
和 一个目标值 target
。请你从 nums
中选出三个整数,使它们的和与 target
最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1:
输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2:
输入:nums = [0,0,0], target = 1
输出:0
提示:
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
优化来自灵神,不得不说,灵神yyds,下面为灵神的题解
16. 最接近的三数之和 - 力扣(LeetCode)
代码
C++
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
int n = nums.size();
int minDiff = INT_MAX;
int ans = 0;
for (int i = 0; i < n - 2; i++) {
int x = nums[i];
// 优化三
if(i > 0 && x == nums[i - 1]){
continue;
}
// 优化一
int res = x + nums[i+1] + nums[i+2];
if(res > target){ // 后面无论怎么选,选出的三个数的和不会比res小
if(res - target < minDiff){
ans = res;
}
break;
}
// 优化二
res = x + nums[n - 1] + nums[n - 2];
if(res < target){ // x 加上后面任意两个数都不超过 s,所以下面的双指针就不需要跑了
if(target - res < minDiff){
minDiff = target - res;
ans = res;
}
continue;
}
// 双指针
int left = i + 1, right = n - 1;
while (left < right) {
int res = x + nums[left] + nums[right];
if (res == target) {
return target;
} else if (res < target) {
if (target - res < minDiff) { // 找到更接近 target 的数
minDiff = target - res;
ans = res;
}
left++;
} else {// res > target
if (res - target < minDiff) { // 找到更接近 target 的数
minDiff = res - target;
ans = res;
}
right--;
}
}
}
return ans;
}
};
Java
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int minDiff = Integer.MAX_VALUE;
int ans = 0;
for (int i = 0; i < n - 2; i++) {
int x = nums[i];
// 优化三
if (i > 0 && x == nums[i - 1]) {
continue;
}
// 优化一
int res = x + nums[i + 1] + nums[i + 2];
if (res > target) { // 后面无论怎么选,选出的三个数的和不会比res小
if (res - target < minDiff) {
ans = res;
}
break;
}
// 优化二
res = x + nums[n - 1] + nums[n - 2];
if (res < target) { // x 加上后面任意两个数都不超过 s,所以下面的双指针就不需要跑了
if (target - res < minDiff) {
minDiff = target - res;
ans = res;
}
continue;
}
// 双指针
int left = i + 1, right = n - 1;
while (left < right) {
res = x + nums[left] + nums[right];
if (res == target) {
return target;
} else if (res < target) {
if (target - res < minDiff) { // 找到更接近 target 的数
minDiff = target - res;
ans = res;
}
left++;
} else { // res > target
if (res - target < minDiff) { // 找到更接近 target 的数
minDiff = res - target;
ans = res;
}
right--;
}
}
}
return ans;
}
}
4.盛最多水的容器
题目链接:11. 盛最多水的容器 - 力扣(LeetCode)
题目描述
给定一个长度为 n
的整数数组 height
。有 n
条垂线,第 i
条线的两个端点是 (i, 0)
和 (i, height[i])
。
找出其中的两条线,使得它们与 x
轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明:**你不能倾斜容器。
示例 1:
输入:[1,8,6,2,5,4,8,3,7]
输出:49
解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
输入:height = [1,1]
输出:1
提示:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
代码
C++
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int left = 0;
int right = n - 1;
int res = 0,area = 0;
while(left < right){
area = (right - left) * min(height[left],height[right]);
res = max(res,area);
if(height[left] < height[right]){
left++;
} else {
right--;
}
}
return res;
}
};
Java
class Solution {
public int maxArea(int[] height) {
int n = height.length;
int left = 0;
int right = n - 1;
int res = 0;
while(left < right){
int area = Math.min(height[left],height[right]) * (right - left);
res = Math.max(res,area);
if(height[left] < height[right]){
left++;
}else{
right--;
}
}
return res;
}
}
5.接雨水
题目链接:42. 接雨水 - 力扣(LeetCode)
题目描述
给定 n
个非负整数表示每个宽度为 1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例 1:
输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例 2:
输入:height = [4,2,0,3,2,5]
输出:9
提示:
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
代码
C++
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
int left = 0, right = n - 1;
int pre_max = 0, suf_max = 0;
int ans = 0;
while (left < right) {
pre_max = max(pre_max, height[left]); // 更新前缀最大值
suf_max = max(suf_max, height[right]); // 更新后缀最大值
if (pre_max < suf_max) { // 柱子雨水高度是该柱子前后缀最高柱子的较小者
ans += pre_max - height[left]; // 当前位置雨水高度减去柱子高度
left++; // 左指针右移
} else {
ans += suf_max - height[right]; // 当前位置雨水高度减去柱子高度
right--; // 右指针左移
}
}
return ans;
}
};
Java
class Solution {
public int trap(int[] height) {
int n = height.length;
int left = 0, right = n - 1;
int pre_max = 0, suf_max = 0;
int ans = 0;
while (left < right) {
pre_max = Math.max(pre_max, height[left]); // 更新前缀最大值
suf_max = Math.max(suf_max, height[right]); // 更新后缀最大值
if (pre_max < suf_max) { // 柱子雨水高度是该柱子前后缀最高柱子的较小者
ans += pre_max - height[left]; // 当前位置雨水高度减去柱子高度
left++; // 左指针右移
} else {
ans += suf_max - height[right]; // 当前位置雨水高度减去柱子高度
right--; // 右指针左移
}
}
return ans;
}
}
同向双指针(滑动窗口)
1.长度最小的子数组
题目链接:209. 长度最小的子数组 - 力扣(LeetCode)
题目描述
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其总和大于等于 target
的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度**。**如果不存在符合条件的子数组,返回 0
。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
思路
滑动窗口
代码
C++
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ans = n + 1;
int left = 0, s = 0;
for (int right = 0; right < n; right++) {
s += nums[right];
while (s >= target) {
ans = min(ans, right - left + 1);
s -= nums[left];
left++;
}
}
return ans <= n ? ans : 0;
}
};
Java
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int ans = n+1;
int left = 0, s = 0;
for(int right = 0;right < n; right++){
s += nums[right];
while(s >= target){
ans = Math.min(ans, right - left +1);
s -= nums[left];
left++;
}
}
return ans <= n ? ans : 0;
}
}
2.乘积小于K的子数组
题目链接:713. 乘积小于 K 的子数组 - 力扣(LeetCode)
题目描述
给你一个整数数组 nums
和一个整数 k
,请你返回子数组内所有元素的乘积严格小于 k
的连续子数组的数目。
示例 1:
输入: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 的子数组。
示例 2:
输入:nums = [1,2,3], k = 0
输出:0
提示:
1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106
思路
滑动窗口
代码
C++
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int n = nums.size();
int ans = 0; // 结果
int left = 0;
int s = 1;
if(k <= 1){
return 0;
}
for(int right = 0; right < n; right++){
s *= nums[right];
while( s >= k){
s /= nums[left];
left++;
}
ans += right - left + 1;
}
return ans;
}
};
Java
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int n = nums.length;
int ans = 0;
int s = 1;
int left = 0;
if(k <= 1){
return 0;
}
for(int right = 0;right < n; right++){
s *= nums[right];
while(s >= k){
s /= nums[left];
left++;
}
ans += right - left + 1;
}
return ans;
}
}
3.无重复字符的最长子串
题目链接:3. 无重复字符的最长子串 - 力扣(LeetCode)
题目描述
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s
由英文字母、数字、符号和空格组成
思路
滑动窗口
代码
C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
int ans = 0, left = 0;
unordered_set<char> window; // 维护当前子串的字符集合
for (int right = 0; right < n; right++) {
char c = s[right];
while (window.count(c)) {
window.erase(s[left]);
left++;
}
window.insert(c);
ans = max(ans, right - left + 1);
}
return ans;
}
};
Java
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0, left = 0;
HashSet<Character> window = new HashSet<>();
for (int right = 0; right < n; right++) {
char c = s.charAt(right);
while (window.contains(c)) { // 判断是否重复
window.remove(s.charAt(left));
left++;
}
window.add(c);
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}