题1

题目：给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素.元素的顺序可以改变.然后返回数组中与 val 不同的元素的数量.

假设 nums 中不等于 val 的元素数量为 k，要通过此题，你需要执行以下操作：

  • 修改 nums 数组，使得 nums 的前 k 个元素包含所有不等于 val 的元素.
  • 返回 k 的值.nums 中的其他元素和数组大小不重要.

方法一：双指针

思路及算法：

由于题目要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上.可以使用双指针：右指针 right 指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置.

如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；

如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位.

整个过程保持不变的性质是：区间 [0,left) 中的元素都不等于 val.当左右指针遍历完输入数组以后，left 的值就是输出数组的长度.

这样的算法在最坏情况下（输入数组中没有元素等于 val），左右指针各遍历了数组一次.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 为序列的长度.我们只需要遍历该序列至多两次.

空间复杂度：O(1).我们只需要常数的空间保存若干变量.

方法二：双指针优化

思路与算法：

如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5]，当 val 为 1 时，我们需要把每一个元素都左移一位.注意到题目中说：「元素的顺序可以改变」.实际上我们可以直接将最后一个元素 5 移动到序列开头，取代元素 1，得到序列 [5,2,3,4]，同样满足题目要求.这个优化在序列中 val 元素的数量较少时非常有效.

实现方面，我们依然使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列.

如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位.如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针 left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止.

当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素.

这样的方法两个指针在最坏的情况下合起来只遍历了数组一次.与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
};

复杂度分析

时间复杂度：O(n)，其中 n 为序列的长度.我们只需要遍历该序列至多一次.

空间复杂度：O(1).我们只需要常数的空间保存若干变量.

题2

给定一个含有 n 个正整数的数组和一个正整数 target .

找出该数组中满足其总和大于等于 target 的长度最小的

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**.**如果不存在符合条件的子数组，返回 0 .

示例 1：

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

方法一：暴力解法（会超时）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

时间复杂度：O(n的平方），其中 n 是数组的长度.需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组.

空间复杂度：O(1).

方法二：前缀和 + 二分查找

方法一的时间复杂度是 O(n的平方)，因为在确定每个子数组的开始下标后，找到长度最小的子数组需要 O(n) 的时间.如果使用二分查找，则可以将时间优化到 O(logn).

为了使用二分查找，需要额外创建一个数组 sums 用于存储数组 nums 的前缀和，其中 sums[i] 表示从 nums[0] 到 nums[i−1] 的元素和.得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于 i 的最小下标 bound，使得 sums[bound]−sums[i−1]≥s，并更新子数组的最小长度（此时子数组的长度是 bound−(i−1)）.

因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性.如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了.

在很多语言中，都有现成的库和函数来为我们实现这里二分查找大于等于某个数的第一个位置的功能，比如 C++ 的 lower_bound.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        vector<int> sums(n + 1, 0); 
        // 为了方便计算，令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            auto bound = lower_bound(sums.begin(), sums.end(), target);
            if (bound != sums.end()) {
                ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

方法三：滑动窗口

在方法一和方法二中，都是每次确定子数组的开始下标，然后得到长度最小的子数组，因此时间复杂度较高.为了降低时间复杂度，可以使用滑动窗口的方法.

定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 nums[start] 到 nums[end] 的元素和）.

初始状态下，start 和 end 都指向下标 0，sum 的值为 0.

每一轮迭代，将 nums[end] 加到 sum，如果 sum≥s，则更新子数组的最小长度（此时子数组的长度是 end−start+1），然后将 nums[start] 从 sum 中减去并将 start 右移，直到 sum<s，在此过程中同样更新子数组的最小长度.在每一轮迭代的最后，将 end 右移.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result=100001;
        int sum=0;
        int i=0;
        int subLength=0;
        for(int j=0;j<nums.size();j++)
        {
            sum+=nums[j];
            while(sum>=target)
            {
                subLength=j-i+1;
                result=result<subLength?result:subLength;
                sum-=nums[i++];
            }
        }
        return result==100001?0:result;
    }
};