双指针法

水桶问题

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。

示例 1：

题解思路

用一句话概括双指针解法的要点：指针每一次移动，都意味着排除掉了一个柱子。
如下图所示，在一开始，我们考虑相距最远的两个柱子所能容纳水的面积。水的宽度是两根柱子之间的距离 d = 8d=8；水的高度取决于两根柱子之间较短的那个，即左边柱子的高度 h = 3h=3。水的面积就是 3 \times 8 = 243×8=24。

如果选择固定一根柱子，另外一根变化，水的面积会有什么变化吗？稍加思考可得：

• 当前柱子是最两侧的柱子，水的宽度 dd 为最大，其他的组合，水的宽度都比这个小。
• 左边柱子较短，决定了水的高度为 3。如果移动左边的柱子，新的水面高度不确定，一定不会超过右边的柱子高度 7。
• 如果移动右边的柱子，新的水面高度一定不会超过左边的柱子高度 3，也就是不会超过现在的水面高度。

由此可见，如果固定左边的柱子，移动右边的柱子，那么水的高度一定不会增加，且宽度一定减少，所以水的面积一定减少。这个时候，左边的柱子和任意一个其他柱子的组合，其实都可以排除了。也就是我们可以排除掉左边的柱子了。
这个排除掉左边柱子的操作，就是双指针代码里的 i++。i 和 j 两个指针中间的区域都是还未排除掉的区域。随着不断的排除，i 和 j 都会往中间移动。当 i 和 j 相遇，算法就结束了。

图解双指针解法的原理

下面我们用更直观的方法来看看“排除掉一根柱子”、“指针移动”究竟代表着什么。
在这道题中，假设一共有 nn 根柱子，编号 0, 1, \dots, n-10,1,…,n−1，高度分别为 H0, H_1, \dots, H{n-1}H_0,_H_1,…,_Hn−1。我们要寻找的是两根柱子 i, ji,j，它们需要满足的约束条件是：

• ii、jj 都是合法的柱子下标，即 0 \le i < n, 0 \le j < n0≤i<n,0≤j<n
• ii 在 jj 的左边，即 i < ji<j

而我们希望从中找到容纳水面积最大的柱子 (i, j)(i,j)。以 n = 8n=8 为例，这时候全部的搜索空间是：

由于 ii、jj 的约束条件的限制，搜索空间是白色的倒三角部分。可以看到，搜索空间的大小是 O(n^2)O(n_2) 数量级的。如果用暴力解法求解，一次只检查一个单元格，那么时间复杂度一定是 O(n^2)_O(n_2)。要想得到 O(n)_O(n) 的解法，我们就需要能够一次排除多个单元格。那么我们来看看，本题的双指针解法是如何削减搜索空间的：
一开始，我们检查右上方单元格 (0, 7)(0,7)，即考虑最左边的 00 号柱子和最右边的 77 号柱子，计算它们之间容纳水的面积。然后我们比较一下两根柱子的高度，关注其中较短的一根。

假设左边的 00 号柱子较短。根据刚才的推理，00 号柱子目前的水面高度已经到了上限。由于 77 号柱子已经是离 00 号柱子最远的了，水的宽度也最大，如果换其他的柱子和 00 号柱子配对，水的宽度只会更小，高度也不会增加，容纳水的面积只会更小。也就是说，00 号柱子和 6, 5, \dots, 16,5,…,1 号柱子的配对都可以排除掉了。记录了 (0, 7)(0,7) 这组柱子的结果之后，就可以排除 00 号柱子了。这相当于 i=0i=0 的情况全部被排除。对应于双指针解法的代码，就是 i++；对应于搜索空间，就是削减了一行的搜索空间，如下图所示。

排除掉了搜索空间中的一行之后，我们再看剩余的搜索空间，仍然是倒三角形状。我们检查右上方的单元格 (1, 7)(1,7)，即考虑 11 号柱子和 77 号柱子，计算它们之间容纳水的面积。然后，比较两根柱子的高度。

假设此时 77 号柱子较短。同理， 77 号柱子已经是离 11 号柱子最远的了，如果换其他的柱子和 11 号柱子配对，水的宽度变小，高度也不会增加，容纳水的面积只会更小。也就是说，77 号柱子和 2, 3, \dots, 62,3,…,6 号柱子的配对都可以排除掉了。记录了 (1, 7)(1,7) 这组柱子的结果之后，就可以排除 77 号柱子了。这相当于 j=7j=7 的情况全部被排除。对应于双指针解法的代码，就是 j—；对应于搜索空间，就是削减了一列的搜索空间，如下图所示。

可以看到，无论柱子 ii 和 jj 哪根更长，我们都可以排除掉一行或者一列的搜索空间。经过 nn 步以后，就能排除所有的搜索空间，检查完所有的可能性。搜索空间的减小过程如下面动图所示：

代码实现

int maxArea(int* height, int heightSize){
int i = 0;
int j = heightSize-1;
int temp = 0;
int max = 0;
while(i<j){             //保证宽度存在
    temp = (j-i)*(height[i]>height[j]?height[j]:height[i]);
    max = max>temp?max:temp;
    if(height[i]<height[j])//左边的决定水面高度  想改变只能舍弃左边柱子
        i++;
    else
        j--;
}
return max;
}

两数之和——有序数组

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值_。_numbers 的下标从1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

题解思路

因为有序，所以可用i，j两个指针，分别指向最初、最末元素，当初始和sum>target说明应缩小加数，即j—；反之亦然。
注意返回的是数组地址，因而需要手动申请一个数组用来储存返回值；
若找不到符合条件的i，j则返回{-1，-1}；

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
int* ret = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;
int i = 0,j = numbersSize-1;
while(i<j){
    int sum = numbers[i]+numbers[j];
    if(sum>target){
        j--;
    }
    else if(sum<target){
        i++;
    }
    else{
        ret[0] = i+1;
        ret[1] = j+1;
        return ret;
    }
}
ret[0] = -1,ret[1] = -1;
return ret;
}

有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

  题解思路

  我们可以使用两个指针分别指向位置 00 和 n-1n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况，读者可以仔细思考其精髓所在。

  int* sortedSquares(int* nums, int numsSize, int* returnSize){
  int *p = (int*)malloc(sizeof(int)*numsSize);
  *returnSize = numsSize;
  for(int i = 0,j = numsSize-1,pos = numsSize-1;i<=j;){
    if(nums[i]*nums[i]>nums[j]*nums[j]){
        p[pos] = nums[i]*nums[i];
        i++;
        pos--;
    }
    else{
        p[pos] = nums[j]*nums[j];
        j--;
        pos--;
    }
  }   
  return p;
  }
  

  两个数组的交集 II

  给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。
我们可以不考虑输出结果的顺序。
进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2y0c2/

可以先将两个数组排序，然后使用双指针（迭代器）

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        vector<int>target;
        for(vector<int>::iterator it1=nums1.begin(),it2=nums2.begin();it1!=nums1.end()&&it2!=nums2.end();)
        {
            if(*it1<*it2 ) it1++;
            else if(*it1==*it2)
            {
                target.push_back(*it1);
                 it1++;
                 it2++;
            }
            else if(*it1>*it2 ) it2++;
        }
        return target;
    }
};

加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：

输入：digits = [0]
输出：[1]

提示：

1 <= digits.length <= 100
0 <= digits[i] <= 9

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2cv1c/

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int len = digits.size();
        for(int i = len - 1;i>=0;i--) {
            if(digits[i] != 9) {
                //如果数组当前元素不等于9，直接加1
                //然后直接返回
                digits[i]++;
                return digits;
            }
            else {
                //如果数组当前元素等于9，那么加1之后
                //肯定会变为0，我们先让他变为0
                digits[i] = 0;
            }
        }
        //除非数组中的元素都是9，否则不会走到这一步，
        //如果数组的元素都是9，我们只需要把数组的长度增加1，并且把数组的第一个元素置为1即可
        digits.insert(digits.begin(),1);
        return digits;
        //第二种增加方法
        /*vector<int> digits(n + 1);
        digits[0] = 1;
        return digits;
        */
    }
};