力扣刷题-数组

力扣 704

二分查找
这道题目可以用暴力解法，也就是遍历数组元素，但是这样做的时间复杂度是$\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

移除元素
这个题目可以用双指针的方法进行解答。假定现在有两个指针，一个叫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

有序数组的平方（双指针）
这个题可以直接先平方后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

长度最小的子数组（双指针）
这个题目可以用滑窗思想进行求解，仍然可以采用双指针，一个起始指针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

螺旋矩阵Ⅱ
这个题的难点在于如何编程实现螺旋顺序的矩阵元素访问。这里假设矩阵的四个顶点分别为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：

起始时Lt → Rb（虽然实际上是Lt → Rt，但Lt和Rb是左右两个相对方向），矩阵遍历下标为 [Rt][i]，因为这里相当于是“ 行 = Rt = 0 ”是定值，“列 = i = Lt → Rb ”是变值。当列遍历完成，Rt++，相当于第0行现在已经填充好了元素，因此Rt需要向下移动一行。
第二步Rt → Lb（虽然实际上是Rt → Rb，但Rt和Lb是上下两个相对方向），矩阵遍历下标为 [i][Rb]，因为这里相当于是“ 列 = Rb = n - 1 ”是定值，“行 = i = Rt → Lb ”是变值。当列遍历完成，Rb- -，相当于第n - 1列现在已经填充好了元素，因此Rb需要向左移动一行。
第三步Rb → Lt，[Lb][i]，Lb- -。
第四步Lb → Rt，[i][Lt]，Lt++。
当矩阵填充值大于$\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;
}