双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。
给你一个整数数组 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 * 1041 <= nums[i] <= 10000 <= k <= 106
class Solution
{
public:
int numSubarrayProductLessThanK(vector<int> &nums, int k)
{
long long tmp = 1ll;
int ans = 0;
// 开一个l和r的双指针
for (int l = 0, r = 0; r < nums.size(); r++)
{
// 每次r指针往右移动的时候，tmp都乘以nums[r]
tmp *= nums[r];
while (l <= r && tmp >= k)
// 如果tmp大于或者等于k了，就要把l指针往右移动，缩小tmp，所以移动l的时候要除以nums[l]
tmp /= nums[l++];
// 每次将结果加到答案里面
ans += r - l + 1;
}
return ans;
}
};设两个指针分别为l和r，另外设置一个变量tmp记录[l,r]内所有数的乘积。最开始l,r都是都在最左面，先向右移动，直到第一次发现 tmp>=k，这时就固定r，右移l，直到tmp<k。那么对于每个r，l是它能延展到的左边界，由于正整数乘积的单调性，此时以r为右端点的满足题目条件的区间个数为 r-l+1个。
对于当前窗口 [l, r]，以 r 结尾的所有子数组的起始点可以是 l, l+1, ..., r，共 r - l + 1 个。例如窗口 [5, 2, 6] 时，以 6 结尾的子数组有 [5,2,6]、[2,6]、[6]，共 3 个，即 r-l+1 = 3。
接下来看一个子序列匹配应用的题：
524. Longest Word in Dictionary through Deleting
Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:
Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"
Example 2:
Input: s = "abpcplea", dictionary = ["a","b","c"]
Output: "a"
Constraints:
s and dictionary[i] consist of lowercase English letters.
1 <= s.length <= 1000
1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 1000
class Solution
{
public:
string findLongestWord(string s, vector<string> &dictionary)
{
// 先按字母序排序
sort(dictionary.begin(), dictionary.end());
int mx = 0; // 设定一下指针和最大长度
string ans = "";
for (int i = dictionary.size() - 1; i >= 0; i--)
{
int x = 0;
for (int j = 0; j < s.size(); j++)
{
if (s[j] == dictionary[i][x])
x++;
}
if (x == dictionary[i].size())
{
if (x >= mx)
mx = x, ans = dictionary[i];
}
}
return ans;
}
};此类问题需要将字符串 s与dictionary[i]进行匹配，判断dictionary[i]是否为s的子序列。解决这种问题只需先将两个指针一个x放在s开始位置，一个j放在dictionary[i]开始位置，如果x==j说明dictionary[i]的第j位已经在s中找到了第一个对应，可以进而检测后面的部分了，那么x和j同时加一。如果上述等式不成立，则dictionary[i]的第j位仍然没有被匹配上，所以只给x加一，在x的后面部分再继续寻找。最后，如果x已经移到了超尾位置，说明整个字符串都可以被匹配上，也就是dictionary[i]是s的一个子序列，否则不是。
利用序列有序性：很多时候在序列上使用双指针之所以能够正确地达到目的，是因为序列的某些性质，最常见的就是利用序列的有序性。
给你一个下标从 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] <= 1000numbers按 非递减顺序 排列-1000 <= target <= 1000- 仅存在一个有效答案
这种问题也是双指针的经典应用了，虽然二分也很方便，但时间复杂度上多一个 logN，而且代码不够简洁。
接下来介绍双指针做法：既然要找到两个数，且这两个数不能在同一位置，那其位置一定是一左一右。由于两数之和固定，那么两数之中的小数越大，大数越小。考虑到这些性质，那我们不妨从两边接近它们。
首先假定答案就是 1 和 n，如果发现 num[1]+num[n]>target，说明我们需要将其中的一个元素变小，而 \mathit{num}[1] 已经不能再变小了，所以我们把指向 n 的指针减一，让大数变小。
同理如果发现 num[1]+num[n]<target，说明我们要将其中的一个元素变大，但num[n] 已经不能再变大了，所以将指向 1 的指针加一，让小数变大。
推广到一般情形，如果此时我们两个指针分别指在 l,r 上，且 l<r, 如果 num[l]+num[r]>target，就将 r 减一，如果 num[l]+num[r]<target，就将 l 加一。这样 l 不断右移，r 不断左移，最后两者各逼近到一个答案。
class Solution
{
public:
vector<int> twoSum(vector<int> &numbers, int target)
{
int r = numbers.size() - 1, l = 0;
vector<int> ans;
ans.clear();
while (l < r)
{
if (numbers[l] + numbers[r] > target)
r--;
else if (numbers[l] + numbers[r] == target)
{
ans.push_back(l + 1), ans.push_back(r + 1);
return ans;
}
else
l++;
}
return ans;
}
};
文章评论