704 二分查找

  题目描述：给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果target存在返回下标，否则返回-1。

  • 示例 1:
    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4
  • 示例 2:
    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1

  这道题目可以用暴力解法，也就是遍历数组元素，但是这样做的时间复杂度是$\small{O(N)}$。因此可以采取二分法对题目进行求解。设定开始查找的范围为[left, right]，比较区间中点mid的值和target的大小，如果小于target说明target在[mid + 1, right]之间，如果大于target说明target在[left, mid - 1]之间。每轮根据区间修改left或right的值，如果left > right，说明数组中没有target目标值，返回-1。知道了二分法的原理，编写下面的代码：

int search(vector<int>& nums, int target)
{
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right)
    {
        int mid = (right - left) / 2 + left;
        int num = nums[mid];
        if(num == target)
        {
            return mid;
        }
        else if(num > target)
        {
            right = mid - 1;
        }
        else left = mid + 1;
    }
    return -1;
}

  此代码的时间复杂度为$\small{O(\mathrm{log}(N))}$。

27 移除元素（双指针）

  题目描述：给你一个数组nums和一个值val，你需要原地移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：
  更改nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。
  返回k。

  • 示例 1：
    输入：nums = [3,2,2,3], val = 3
    输出：2, nums = [2,2,,]
    解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
    你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
  • 示例 2：
    输入：nums = [0,1,2,2,3,0,4,2], val = 2
    输出：5, nums = [0,1,4,0,3,,,_]
    解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
    注意这五个元素可以任意顺序返回。
    你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

  这个题目可以用双指针的方法进行解答。假定现在有两个指针，一个叫slow，一个叫fast，他们起始都指向数组nums的第一个元素nums[0]，然后判定nums[fast]是否与val相等，如果相等，fast++，如果不相等就把nums[fast]的值给nums[slow]，fast++，slow++。可以看到，这个操作实际上就是将非val的元素向前挪动，覆盖掉值为val的元素。这样无论nums数组后的元素是什么，只要保证返回的前k个元素不包含val就行。因此循环判定的条件就是fast < nums.size()。代码编写如下：

int removeElement(vector<int>& nums, int val)
{
    int slow = 0, fast = 0;
    while(fast < nums.size())
    {
        if(nums[fast] != val)
        {
            nums[slow++] = nums[fast++];
        }
        else fast++;
    }
    return slow;
}

  时间复杂度为$\small{O(N)}$，空间复杂度为$\small{O(1)}$。

977 有序数组的平方（双指针）

  题目描述：给你一个按非递减顺序排序的整数数组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]

  这个题可以直接先平方后sort排序的方法，但是这样做的时间复杂度为$\small{O(n\mathrm{log}n)}$，空间复杂度为$\small{O(\mathrm{log}n)}$。代码如下：

vector<int> sortedSquares(vector<int>& nums)
{
    for(int i = 0; i < nums.size(); i++)
    {
        nums[i] *= nums[i];
    }
    sort(nums.begin(), nums.end());
    return nums;
}

  其实也可以采用双指针的办法。题目告诉了数组是有序的，那么设定指针left和指针right，并新建一个数组res，大小和nums一样。left指向nums第一个元素，right指向nums的最后一个元素。如果nums[left]^2 > nums[right]^2，那么就把left的运算结果给res最右侧未被赋值的元素k，此时left++，k- -。同理，当nums[left]^2 < nums[right]^2 ，那么就把right的运算结果给res最右侧并right- -，k- -。以此类推。

vector<int> sortedSquares(vector<int>& nums)
{
    vector<int> res(nums.size(), 0);
    int k = nums.size();
    int left = 0, right = nums.size() - 1;
    while(left <= right)
    {
        if(nums[left] * nums[left] <= nums[right] * nums[right])
        {
            res[k--] = nums[right] * nums[right];
            right--;
        }
        else
        {
            res[k--] = nums[left] * nums[left];
            left++;
        }
    }
    return res;
}

  此代码的时间复杂度为$\small{O(n)}$，空间复杂度为$\small{O(1)}$。

209 长度最小的子数组（双指针）

  给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl,numsl+1,…,numsr-1,numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。

  • 示例 1：
    输入：target = 7, nums = [2,3,1,2,4,3]
    输出：2
    解释：子数组 [4,3] 是该条件下的长度最小的子数组。
  • 示例 2：
    输入：target = 4, nums = [1,4,4]
    输出：1
  • 示例 3：
    输入：target = 11, nums = [1,1,1,1,1,1,1,1]
    输出：0

  这个题目可以用滑窗思想进行求解，我们仍然可以采用双指针，一个起始指针i和末尾指针j，以示例1为例。开始i和j都指向nums[0]，然后j++，统计i和j之间元素和sum。当j=3时，sum=8>7，此时长度为res=4。为了找到最小的长度，令i++，sum=6，不符合要求。此时j++，开启下一轮的查找。此时sum=10，res=4，令i++，sum=7，res=3；i++，sum=6，不符合要求……以此类推，直到当i=5，j=6，sum=7，res=2。得到最后结果。代码实现如下：

int minSubArrayLen(int target, vector<int>& nums)
{
    int res = INT32_MAX;//设置窗口最大值，以方便比较
    int i = 0;
    int sum = 0;
    int windsize = 0;
    for(int j = 0; j < nums.size(); j++>)
    {
        sum += nums[j];
        while(sum >= target)
        {
            windsize = j - i + 1;
            res = res > windsize ? windsize : res;
            sum -= nums[i++];
        }
    }
    return res == INT32_MAX ? 0 : res;
}

59 螺旋矩阵Ⅱ

  给你一个正整数$\small{n}$，生成一个包含$\small{1}$到$\small{n^2}$所有元素，且元素按顺时针顺序螺旋排列的$\small{n \times n}$正方形矩阵matrix。

  • 示例 1：
    示例1
    输入：n = 3
    输出：[[1,2,3],[8,9,4],[7,6,5]]
  • 示例 2：
    输入：n = 1
    输出：[[1]]

  这个题的难点在于如何编程实现螺旋顺序的矩阵元素访问。这里我们假设矩阵的四个顶点分别为left_Top(Lt)、left_Bottom(Lb)、Right_Top(Rt)、Right_Bottom(Rb)，并将他们的值设置为：

int Lt = 0;
int Lb = n - 1;
int Rt = 0;
int Rb = n - 1;

  设定Lt方向为 → ， Rt ↓ ， Rb ← ， Lb ↑ 。这里四个顶点的坐标并不重要，重要的是这四个顶点标明了矩阵的旋转方向和坐标边界值。下面对坐标边界值进行说明。
  设定Lt和Rb是两个相对方向，那么列方向上坐标边界值就是Lt = 0和Rb = n - 1。同理，Lb和Rt是另外两个相对的方向，行方向上坐标边界值就是Rt = 0，Lb = n - 1。
  知道了这些条件，我们现在加入一个变量 i：

  1. 起始时Lt → Rb（虽然实际上是Lt → Rt，但Lt和Rb是左右两个相对方向），矩阵遍历下标为 [Rt][i]，因为这里相当于是“ 行 = Rt = 0 ”是定值，“列 = i = Lt → Rb ”是变值。当列遍历完成，Rt++，相当于第0行现在已经填充好了元素，因此Rt需要向下移动一行。
  2. 第二步Rt → Lb（虽然实际上是Rt → Rb，但Rt和Lb是上下两个相对方向），矩阵遍历下标为 [i][Rb]，因为这里相当于是“ 列 = Rb = n - 1 ”是定值，“行 = i = Rt → Lb ”是变值。当列遍历完成，Rb- -，相当于第n - 1列现在已经填充好了元素，因此Rb需要向左移动一行。
  3. 第三步Rb → Lt，[Lb][i]，Lb- -。
  4. 第四步Lb → Rt，[i][Lt]，Lt++。
  5. 当矩阵填充值大于$\small{n \times n}$说明已经填充完毕，退出循环。

  通过上述步骤我们就实现了矩阵的螺旋顺序访问。这个原理不仅可以用于顺时针，还可以用于逆时针。

vector<vector<int>> generateMatrix(int n)
{
    vector<vector<int>> res(n, vector<int>(n));
    int Lt = 0, Lb = n - 1, Rt = 0, Rb = n - 1;
    int count = 1;
    int flag = n * n;
    while(count <= flag)
    {
        for(int i = Lt; i <= Rb; i++)
        {
            res[Rt][i] = count++;
        }
        Rt++;
        for(int i = Rt; i <= Lb; i++)
        {
            res[i][Rb] = count++;
        }
        Rb--;
        for(int i = Rb; i >= Lt; i--)
        {
            res[Lb][i] = count++;
        }
        Lb--;
        for(int i = Lb; i >= Rt; i--)
        {
            res[i][Lt] = count++;
        }
        Lt++;
    }
    return res;
}