文章目录
- 1、移动零
- 2、复写零
- 3、快乐数
- 4、盛最多水的容器
- 5、有效三角形的个数
- 6、和为s的两个数
- 7、三数之和
- 8、四数之和
需要理解的是，双指针并非只有指针，双指针的意思是两个位置。比如对于数组来说，两个下标也是双指针。当然，也可以说，双指针是一种思想。
关于详细的考量，会在题目中展现。常用指针名字：dest和src，left和right，prev和cur，slow和fast
1、移动零
链接
题目要求很清晰，要求0全部在最后，0前面全部是非0数，那么这时候双指针的作用区分就很明确。左指针的左边都是非0数，左指针的右边则是0。这是一个初步的整体划分，先定义 左右指针为a和b。
接下来想想逐步的操作，两个下标位置，也就是两个int数，指向两个数组里的数，然后判断是否为0；一方为0，就要交换一下，让0来到a的右边，也就是让b的位置的数字是0，然后继续遍历。这样一想，随着逐渐的往后走，b指针的右边就是待处理的部分，而ab之间是0，a左边则是非0数；这样3个区间就划分好了。
a指针指向非0数，左边都是非0数，所以a指针指向最后一个非0数，b指针左边都是0，右边是待处理的，所以b指针指向最后一个0；如果走完整个空间，就没有待处理的部分了。
数组最初的位置可以不是0，我们可以让a指针初始化为-1。因为最一开始我们并不知道是否有非0数，所以不如让a为-1，b位置是0，b开始判断是否为0；如果num[b]是0，那么b就++，a不动，这样ab之间就有0了；如果是非0，那就得交换一下，但是需要a指针往前走一步再交换，不能这样访问num[-1]，而且如果一直是非0数，a++后再去交换，就相当于是原地交换数值，不发生变化。
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
int n = nums.size();
int prev = -1, cur = 0;
while(cur < n)
{
if(nums[cur] != 0)
{
swap(nums[++prev], nums[cur]);
}
++cur;
}
}
};
2、复写零
链接
这道题一个简单的思路是再开一个数组，一个指针指向原数组，另一个指向新数组，原数组只要出现0，新数组内就写两个0，不是就写一个，直到新数组全部填完。假设是数组[1, 0, 2, 3]，a指针指向原数组，b指针指向新开的初始化好的数组。a为1，b就填1；a走到0，b填两个0，b来到第二个0，a来到2；a为2，b填2。
两个数组的情况转成一个的。需要注意的是，0后的数字不能直接覆盖掉，而只是写两遍0，然后接着下一个数字。所以我们得保证其它数字不会被覆盖掉。像这样不能覆盖的问题，有一个常用想法就是从后向前走。为了不被覆盖，先把要复写的数确定下来，这样b指针指向最后一个位置，a指针指向前面某个位置，无论怎样，a都每次往前走一步，而如果有0，b就走两步，否则走一步。
在找最后一个要复写的数的过程中，a指针指向0位置，而b指针指向-1。我们定义b指针是指向结果的，也就是原数组的某个数在结果中应当待的位置，a为非0，b就一步；a为0，b就走两步；当b走到末尾时，也就是结果数组中最后一个数的位置，而此时a应当指向填写这个位置的数。综合考虑，b在-1位置是合适的。可以代入例子来观察。在每一次b指针走动后都去判断是否到了最后一个位置，到了就退出循环，没到就让a++。
但是按照这个思路，还是有问题，这个问题就越界问题。b指针不会乖乖地到数组末尾停止，而是可能会越界。如果在后面，a位置的数都是非0数，那么b不会越界，因为它会乖乖地走到末尾，然后一判断，等于n - 1，那就退出；一旦越界，就说明a指向了一个0，b在n - 2的位置，然后走两步来到了n，所以b只会越界到n位置，因为如果在n - 1时就会退出，也不会走到n + 1位置。面对这个情况，就和归并排序处理边界情况一样，简单操作一下即可：将数组最后一个位置置为0，然后a往前走一步，b往前走两步，回到正确的位置，并继续往前判断并填写。
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int n = arr.size();
int prev = 0, cur = -1;
while(cur < n)
{
if(arr[prev]) ++cur;
else cur += 2;
if(cur >= n - 1) break;
++prev;
}
if(cur == n)
{
arr[n - 1] = 0;
cur -= 2;
--prev;
}
while(cur >= 0)
{
if(arr[prev]) arr[cur--] = arr[prev--];
else
{
arr[cur--] = 0;
arr[cur--] = 0;
--prev;
}
}
}
};
3、快乐数
链接
这道题是怎么和双指针有关的？
先看一下题。快乐数没有公式，所以我们只能从代码上找思路。一个暴力解法就是直接算，算到1为止。但如果它不是快乐数，要在什么时候停止计算？这就是一个问题，我们要找的就是一个暂停条件。
如果不是快乐数，就会一直循环。对此能想到的停止办法就是参考环形队列，环形链表：定义快慢指针，然后快指针每一步都比慢指针走得多，让快追慢，追上并且在整个过程也没有出现1，就说明这不是快乐数。为什么？fast是如何追上slow的？fast能追上slow说明，fast又走到了开头位置，也就是slow开始的位置，然后追上slow。也就是说，fast走完了一整个循环过程，而这之中都没有出现1，那肯定就不是快乐数。
这里的快慢指针就代表计算出来的数，比如slow计算一次而fast计算两次。由于停止的条件是slow等于fast，所以为了能够进入，fast和slow再初始化时就不能相等，可以让fast先计算一次，反正最后都是会追上slow。
class Solution {
public:
int bitSum(int n)
{
int sum = 0, ret = 0;
while (n)
{
ret = n % 10;
sum += ret * ret;
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
if(n == 1) return true;
int s = n, f = bitSum(n);
while(s != f)
{
s = bitSum(s);
if(s == 1) return true;
f = bitSum(bitSum(f));
if(f == 1) return true;
}
return false;
}
};
也可以不在while里写判断，出来判断return s == 1或者判断f。
4、盛最多水的容器
链接
这道题是一道练习，只放代码，不写思路。
class Solution {
public:
int maxArea(vector<int>& height) {
int n = height.size();
int l = 0, r = n - 1;
int res = 0;
while(left < right)
{
res = max(res, (r - l) * min(height[l], height[r]));
if(height[l] > height[r]) --r;
else ++l;
}
return res;
}
};
5、有效三角形的个数
链接
由于三角形三条边需要满足a + b > c，所以O(N)的时间复杂度难以实现，即使固定住一个数，另外两个数也得挨个查看是否满足条件，不过这之中可以减少一些重复的遍历。
首先为了方便后序的遍历，先从小到大排序一下；然后从后往前走，固定最大的那个数，设定k为n - 1，剩下两个数就从前面这几个数中挑，所以k必然要至少为2，留出来两个数，设定前面两个数为i和j，如果nums[i] + nums[j] > nums[k]，那就满足条件，当然也可以改成减法判断，这样就避免数值过大。
k固定后，i和j在运动。为了更有效地判断所有可能，让i = 0，j = k - 1，所以此时就能看出来，j肯定是k前面的最大数字，接着判断，如果不满足条件，j不需要更改，因为已经最大了，那么就增加i，直到满足条件就停下。此时nums[i] nums[j] nums[k]就是能组合成三角形的三条边，并且i继续增加也肯定满足条件，所以此时就可以直接加上 j - i，这就是从在j和k固定的情况下，符合条件的所有三元组个数。
这次结束后，j就往前走一步，继续按照上面的步骤去判断。k当然还是固定的，j变成第二个大的数，那么i？i其实也不用改变位置，因为之前更大的j和i前面的数字相加都不满足条件，那么现在更小的j也更不可能满足，所以只移动j就行了，然后从i现在的位置开始继续往后挨个判断。
这样的做法也是嵌套循环，只是减少了一些循环次数。对于k固定后，i和j的变化，以及三角形判断，还有更快的办法，这需要用到一些别的公式，可自行看力扣解析。
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), count = 0;
int i = 0, j = 0, k = 0;
for(k = n - 1; k >= 2; --k)
{
i = 0, j = k - 1;
while(i < j)
{
if(nums[i] + nums[j] > nums[k])
{
count += j - i;
--j;
}
else ++i;
}
}
return count;
}
};
6、和为s的两个数
链接
这道题可以用双指针来完成，但更多人想到的是哈希吧？这道题只写双指针的思路，哈希方法只写代码。
双指针的思路脱胎于暴力枚举。枚举就是算所有的数字，看看有没有符合要求的，而双指针就是有所选择地计算。
数组本身是升序的。定义ab两个位置，分别指向最小数和最大数，如果将ab相加后依然小于目标值，那么最大值不需要变，因为它已经最大了，所以只需要改变让a++，a指向的值变大，再次判断；如果大于目标值，那就让b–。如果等于，就找到了，直接返回。这里仍然使用减法来判断。
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array, int sum) {
if(array.empty()) return {};
int l = 0, r = array.size() - 1;
int res = 0;
while(l < r)
{
res = sum - array[l];
if(res < array[r]) --r;
else if(res > array[r]) ++l;
else return {array[l], array[r]};
}
return {};
}
};
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array, int sum) {
if(array.empty()) return {};
unordered_map<int, int> um;
int n = array.size(), ret = 0;
for(int i = 0; i < n; i++)
{
ret = sum - array[i];
if(um.find(ret) == um.end())
{
um[array[i]] = i;
}
else return {ret, array[i]};
}
return {};
}
};
无论从时间还是空间上来看，双指针都明显优于哈希表。
7、三数之和
链接
两数之和为起点。
仔细看一下题，三个数不能相等，并且有相同的三元组只能有一个，比如-1 0 1和1 0 -1，只有有一个作为结果，另一个抛弃。
可以看出来，我们需要去重，在操作之前先对数组排序。用set去重是可行的，但这里不用多用别的容器，仅在这个数组上边判断边去重。
这道题与 和为s的两个数思路很像，我们先固定一个数，在剩下的区间内找符合条件的两个数即可，并且要找到所有的符合条件的组合；三个数都需要去重。不过如果我们固定的数是一个正数，那么它肯定不可能有对应的组合，因为后面的数都是正数，不可能相加为0。
另外一个重要的问题是越界，在代码中体现：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
int i = 0, j = 0, k = 0;
int sum = 0;
sort(nums.begin(), nums.end());
vector<vector<int>> res;
while(i < n)
{
if(nums[i] > 0) break;//小优化
j = i + 1, k = n - 1;
while(j < k)
{
sum = nums[i] + nums[j] + nums[k];
if(sum > 0) --k;//大于就让最大的数k减小
else if(sum < 0) ++j;//小于就让较小的j增加, 因为i固定
else
{
res.push_back({nums[i], nums[j++], nums[k--]});
//去重
while(j < k && nums[k] == nums[k + 1]) --k;
while(j < k && nums[j] == nums[j - 1]) ++j;
}
}
//i去重, 如果是for循环就把i++给去掉, 要不会越界
++i;
while(i < n && nums[i] == nums[i - 1]) i++;//i < n, 防止后面都是0, i直接出去了
}
return res;
}
};
去重操作可以根据自己的思路去改变写代码的位置。
8、四数之和
链接
经历了和为s的两个数以及三数之和，四数之和也有所思路。三数之和以及四数之和都有一个基于暴力而升级的解法，就是排序 + set去重 + 暴力枚举。
四数之和也是利用双指针，或者说多指针。先固定一个数a，然后再固定一个数b，这样就剩下两个数了，然后运用找两数的方法去做。
当然，这个方法也有点暴力。它要处理的问题同样是去重，越界。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
long long ret = 0;
int n = nums.size(), sum = 0;
int i = 0, j = 0, l = 0, r = 0;
while(i < n)
{
j = i + 1;
while(j < n)
{
l = j + 1, r = n - 1;
ret = (long long)target - nums[j] - nums[i];
while(l < r)
{
sum = nums[l] + nums[r];
if(sum > ret) --r;
else if(sum < ret) ++l;
else
{
res.push_back({nums[i], nums[j], nums[l++], nums[r--]});
//去重
while(l < r && nums[l] == nums[l - 1]) ++l;
while(l < r && nums[r] == nums[r + 1]) --r;
}
}
++j;
while(j < n && nums[j] == nums[j - 1]) ++j;
}
++i;
while(i < n && nums[i] == nums[i - 1]) ++i;
}
return res;
}
}
long long是为了解决力扣例子的中的数字超大问题。
结束。
