移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

思路

左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), l = 0, r = 0;
        while (r < n) {
            if (nums[r]) swap(nums[l], nums[r]), l ++;
            r ++;
        }
    }
};

盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

思路

从暴力方面来讲，一步步枚举容器容纳水量，我发现总是会有最大水量小于之前枚举的情况，一定要排除不必要枚举的情况

• i指向0，j指向n-1
• res = max(res, min(h[i],h[j]) * (j - i) )
• h[i] < h[j] 则i往中间靠，否则j往中间靠
• 直到i >=j 算法结束，输出res

证明短柱子往中间移动：

移动结果一：
比最短的柱子h 依然高，此时无论这个柱子再高，
得到的结果都是h，因为我们要的是最短的，
所以不仅宽度w减少了，高度h还没变，
结果肯定变小，这是不符合的.

移动结果二：
比最短的柱子h矮了，此时h变得更小了，w也减小，就更不可能了。 
所以只有移动短的柱子才有可能比原来的结果大，
因为虽然宽度w在减小，但可能h变大，
w*h整体才有可能变大。
h变小的话可能整体变小，但不影响，因为我们已经记录下了最大值了。所以综上只能移动短的柱子

我之前做的双指针题目是基于一个变量i，
另一个变量j随着i运动，运动过程中满足一定的性值，这道题带有缩小解空间味道，也是卡了我很久

#include <bits/stdc++.h>
using namespace std;

vector<int>v;
int maxArea(vector<int>& height) {
    int res = 0;
    int i = 0, j = height.size() - 1;
    while (j > i)
    {
        int w = j - i;
        int h = min(height[j], height[i]);
        if (height[i] < height[j]) i ++;
        else j --;
        res = max(w * h, res);
    }
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) {
        int x;
        scanf("%d", &x);
        v.push_back(x);
    }
    printf("%d\n", maxArea(v));
}

三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

思路

解空间有重复情况，无非是枚举变量i 和 j 时，nums[i] = nums[j];

哈希解法中我被卡了，处理细节方面很多，没办法第一时间想到位

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>>res;
        int n = nums.size();
        if (n < 3 || nums.front() > 0 || nums.back() < 0) return res;
        for (int i = 0; i < n - 2; i ++ ) {
            if (nums[i] > 0) break;
            if (i && nums[i] == nums[i - 1]) continue;
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
            int l = i + 1, r = n - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (s == 0) {
                    res.push_back({nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l + 1]) l ++;
                    l ++;
                    while (l < r && nums[r] == nums[r - 1]) r --;
                    r --;
                }
                else if (s < 0) l ++;
                else r --;
            }
        }
        return res;
    }
};

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

c++

#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> v;
int trap(vector<int>& h) {
    int n = h.size();
    int l = 0, r = n - 1;
    int lh = 0, rh = 0;
    int res = 0;
    while (l < r) {
        int water = min(lh, rh);
        if (h[l] <= water) {
            res += water - h[l];
            l ++;
            continue;
        }
        if (h[r] <= water) {
            res += water - h[r];
            r --;
            continue;
        }
        lh = max(lh, h[l]);
        rh = max(rh, h[r]);
    }
    return res;
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) {
        int x;
        scanf("%d", &x);
        v.push_back(x);
    }
    printf("%d\n", trap(v));
}

上面几题思想核心一致，但是处理细节挺方便的，有些哈希解法比较难想