4th,Aug

1.二分法：从有序无重复数组中找到 target，要求 logn 时间复杂度

数组：704.二分查找

暴力不满足时间复杂度要求，二分法的关键是明确区间定义，通常有两种思路：

  • A . 左闭右闭区间，定义 right 初始值为 nums.size()-1，每次的 right 右边界都是可以被取到的；循环条件为：while (left <= right)，因为当left==right，区间[left, right]依然有效，所以用 <=；选择条件只需记住：要选择能把边界包括在区间搜索范围内的方式计算新的边界，如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0;
            int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
            while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=
                int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
                if (nums[middle] > target) {
                    right = middle - 1; // target 在左区间，所以[left, middle - 1]
                } else if (nums[middle] < target) {
                    left = middle + 1; // target 在右区间，所以[middle + 1, right]
                } else { // nums[middle] == target
                    return middle; // 数组中找到目标值，直接返回下标
                }
            }
            // 未找到目标值
            return -1;
        }
    };

  • B.左闭右开区间（第一次做题自己自然的思路），我们知道 right 如果等于 nums.size()是不能取到 nums[right]的，所以我们搜索的区间是[left, right)，对于循环跳出条件，只要 left =right 那说明一定没有搜索到 target，所以用<就行，选择条件也只需记住：要选择能把边界包括在区间搜索范围内的方式计算新的边界，如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0;
            int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)
            while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 <
                int middle = left + ((right - left) >> 1);
                if (nums[middle] > target) {
                    right = middle; // target 在左区间，在[left, middle)中
                } else if (nums[middle] < target) {
                    left = middle + 1; // target 在右区间，在[middle + 1, right)中
                } else { // nums[middle] == target
                    return middle; // 数组中找到目标值，直接返回下标
                }
            }
            // 未找到目标值
            return -1;
        }
    };

2.双指针法：移除目标元素

数组：27.移除元素

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。快指针：寻找新数组的元素，新数组就是不含有目标元素的数组；慢指针：指向更新新数组下标的位置。关键的一个语句是：nums[slowIndex++] = nums[fastIndex]每次循环 fastindex 一定会+1，而 slowindex 只有在不匹配时才会++，所以 slow 指针一定不会追上 fast，代码如下：

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

数组：977.有序数组的平方

第一次遇到这个题的我解决思路是逐个乘方，然后 sort，如下：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i = 0; i<nums.size(); i++){
            nums[i] = nums[i]*nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

但是该题的最佳题解也是用双指针法，具体的逻辑是那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。此时可以考虑双指针法了，i指向起始位置，j指向终止位置,如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int i = 0 ;
        int j = nums.size() - 1 ;
        int k = nums.size() - 1 ;
        vector<int> result(nums.size(),0);//注意要赋初值，否则只能 push_back 输入,不能访问下标输入
        while(k>=0){
            if(nums[i]*nums[i] < nums[j]*nums[j]){
                result[k--] = nums[j]*nums[j];
                j--;
            }
            else{
                result[k--] = nums[i]*nums[i];
                i++;
            }
        }
        return result;
    }
};

3.滑动窗口法：解决数组中和子数组性质相关的问题

数组：209.长度最小的子数组

依旧起手暴力算法，刚看到题想出来的题解是：管他丫的直接两个 for，ps：然后现在力扣更新了数据，暴力已经过不了了

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 count = INT_MAX;
        for(int i = 0;i<nums.size();i++){
            if(nums[i] < target){
            int sum = 0;
            for(int j = i;j<nums.size();j++){
                sum = sum + nums[j];
                if((sum >= target)&&((j-i+1)<count)){
                    count = j-i+1;
                    break;
                }
            }
            }
            else return 1;
        }
        return count == INT32_MAX ? 0 : count;
    }
};

该问题是典型的考察数组子数组的性质（这个题是子数组的和）的问题，可以通过滑动窗口来实现，一个窗口边界在左，一个在右，满足条件之前移动右边界，满足后移动左边界，每次满足记录最短子数组长度，最后取最小值返回；(right 是一直往右走不回头的，每次满足条件后，移动 left 直至不满足，然后重新移动 right)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int length = INT_MAX;
        for(right = 0;right<nums.size();right++){
            sum = sum + nums[right];
            while(sum >= target){
                length = min((right -left + 1),length);
                sum -= nums[left];
                left++;
            }
        }
        return length==INT_MAX? 0 : length;
    }
};
4.前缀和

题目链接

最直观的想法就是给一个区间，然后 把这个区间的和都累加一遍不就得了，是一道简单不能再简单的题目。但提交时会发现超时了，我们可以把每次计算和的这个循环的过程变成简单的单次减法，只需要一次循环计算前缀和，就可以节省大量时间；（该题是 ACM 模式，自己写输入输出和宏）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    vector<int> p(n);
    int presum = 0;
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
        presum += vec[i];
        p[i] = presum;
    }

    while (cin >> a >> b) {
        int sum;
        if (a == 0) sum = p[b];
        else sum = p[b] - p[a - 1];
        cout << sum << endl;
    }
}

二维的前缀和思想是一样的，例题如下

题目链接