双指针一般是作为暴力算法的优化而存在。
双指针比起暴力算法减少时间复杂度的答案：
解决方案：
示例 1：
- 1 双指针获取信息的范围更广。
- 2 双指针需要前提条件才能获取更广的信息范围，故一般有前提提示我们使用双指针，例如“已经排好序”…….
1 相向双指针
1.1 两数之和II
给你一个下标从 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] 。解题思路：
- 1 为什么双指针获取信息的范围更广：
- 1.1 如果我们使用暴力迭代，则循环1为数字1，循环2为数字2，则暴力迭代的信息范围为range(1)
- 1.2 如果使用双指针，左边指针指向最小的数，右边指针指向最大的数，则双向指针的信息范围为range(n)
- 2 使用双指针的前提条件：数组以按非递减顺序排列
- 3 如果nums[left]+nums[right]>target, 则left++，否则right–
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int left = 0, right = numbers.size()-1;
while(left < right){
if (numbers[left]+numbers[right] == target) return {left+1, right+1};
else if (numbers[left]+numbers[right] > target) right--;
else left++;
}
return {};
}
};1.2 三数之和
给你一个整数数组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] 。 注意，输出的顺序和三元组的顺序并不重要。解题思路：
- 1 可以遍历一个数，剩下的两个数使用两数之和II的方法寻找。
- 2 由于需要去重，故先将整数数组进行排序。
- 2.1 第一个数的去重，第二次遇到则跳过
- 2.2 第二个数的去重，第二次遇到则跳过
- 2.3 第三个数的去重，第二次遇到则跳过
- 1 第一个数去重时需要注意i需要大于0，否则nums[i-1]会溢出
- 2 第二三个数去重需要在已经匹配到答案的情况下，否则不需要去重。
- 3 匹配到3个数之后，left++和right–，left和right都需要变化。
- 4 二三个数去重时需要使用while。
class Solution {
public:
vector<vector<int>> result;
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
for(int i=0; i<nums.size()-2; i++){
// 1 第一个数去重, 注意i>0
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i+1, right = nums.size()-1;
while(left < right){
if (nums[i] + nums[left] + nums[right] > 0)
right--;
else if (nums[i] + nums[left] + nums[right] < 0){
left++;
}
else {
result.push_back({nums[i], nums[left], nums[right]});
// 此时left和right都需要变化
left++; right--;
// 2 第二个数去重
while (left<right && nums[left] == nums[left-1]) left++;
// 3 第三个数去重
while (left<right && nums[right] == nums[right+1]) right--;
}
}
}
return result;
}
};1.3 四数之和
给你一个由n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Notes:
- 1 相比三数之和，使用两个数进行遍历。
- 2 去重时，针对第二个数，需要j-i>1，为了防止这类情况[-1, -1, 1, 1]。判断重复时，j的前面必须遍历过一个数。
class Solution {
public:
vector<vector<int>> result;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if (nums.size() < 4) return {};
sort(nums.begin(), nums.end());
for(int i=0; i<nums.size()-3; i++){
// 1 第一个数去重
if (i > 0 && nums[i] == nums[i-1]) continue;
for(int j=i+1; j<nums.size()-2; j++){
// 2 第二个数去重
if (j - i > 1 && nums[j] == nums[j-1]) continue;
int left = j+1, right = nums.size()-1;
while(left < right){
if ((long) nums[i] + nums[j] + nums[left] + nums[right] > target)
right--;
else if ((long) nums[i] + nums[j] + nums[left] + nums[right] < target){
left++;
}
else {
result.push_back({nums[i], nums[j], nums[left], nums[right]});
left++; right--;
// 2 第二个数去重
while (left<right && nums[left] == nums[left-1]) left++;
// 3 第三个数去重
while (left<right && nums[right] == nums[right+1]) right--;
}
}
}
}
return result;
}
};1.4 盛水最多的容器
给定一个长度为n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
解决方案：
- 1 left和right之间找最大面积
- 2 left和right谁短就先更新谁。
class Solution {
public:
int maxArea(vector<int>& height) {
int result = 0;
int left = 0, right = height.size()-1;
while(left < right){
int area = (right-left) * min(height[left], height[right]);
result = max(result, area);
if (height[left] > height[right]) right--;
else left++;
}
return result;
}
};1.5 最长回文子串
给你一个字符串s，找到 s 中最长的 回文子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。解题思路：
- 1 上面4题的解题思路包括判断回文子串都是从数组两段往里面遍历，该题不同于判断回文子串，寻找最长回文子串，故从内往外扩散遍历。
- 2 由于扩散遍历的中点有两种情况，奇数数组单中点，偶数数组双中点，并行遍历寻找最长的回文子串。
class Solution {
public:
string palindrome(string s, int left, int right){
while(left>=0 && right<s.size() && s[left] == s[right]){
left--; right++;
}
return s.substr(left+1, right-left-1);
}
string longestPalindrome(string s) {
string result = "";
for(int i=0; i<s.size(); i++){
string s1 = palindrome(s, i, i);
string s2 = palindrome(s, i, i+1);
result = result.size() > s1.size() ? result : s1;
result = result.size() > s2.size() ? result : s2;
}
return result;
}
};2 同向双指针
同向双指针也可以看成滑动窗口，可以解决子数组，子串等问题。2.1 长度最小的子数组
给定一个含有n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4] 输出：1解题思路：
- 1 使用right当做数组的右端点，left作为数组的左端点，先扩大右端点，再缩小左端点。
- 2 当右端点扩大到子数组和大于target时，开始缩小左端点。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT_MAX;
int total = 0;
int left = 0;
for(int right = 0; right < nums.size(); right++){
total += nums[right];
while(total >= target){
result = min(result, (right-left+1));
total -= nums[left];
left++;
}
}
return result == INT_MAX? 0 : result;
}
};2.2 乘积小于k的子数组
给你一个整数数组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 的子数组。解题思路：
- 1 具体需要明白以right为右边界的子数组中的结果为right-left+1, 举例[l, r] -> [l, r] + [l+1, r]…[r, r]个子数组。
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if (k <= 1) return 0;
int result = 0;
int total = 1;
int left = 0;
for(int right=0; right<nums.size(); right++){
total *= nums[right];
while(total >= k){
total /= nums[left];
left++;
}
result += right - left + 1;
}
return result;
}
};2.3 无重复字符的最长子串
给定一个字符串s ，请你找出其中不含有重复字符的 最长 子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。