代码随想录二刷总结复盘 day01

数组章节：

数组基础理论：

(1) 数组主要考察对于代码的掌控能力

(2) 数组是存放在连续内存空间上的相同类型的数据集合(数组内存空间的地址是连续的)

(3) 数组可以方便的通过下标索引的方式获取到下标对应的数据(数组下标都是从0开始的)

(4) 数组的元素是不能删的，只能覆盖

704.二分查找

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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

1. for循环遍历整个数组，如果数组中存在与目标值相等的元素，那么就返回该值在数组中的索引

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == target) return i;
        }
        return -1;

    }
};

2. 双指针：一个指针指向数组首部，另一个指针指向数组尾部，如果中间数大于目标值，右指针改变位置，如果中间数小于目标值，左指针改变位置，找不到就返回-1

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

    }
};

35.搜索插入位置

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

????????给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

????????个人感觉这道题目的关键在于理解插入位置就是第一个大于等于目标值的位置。在数组中插入目标值，一共就以下四种情况

（1）插入元素在数组左侧

（2）插入元素在数组中间

（3）插入元素就是数组中的元素

（4）插入元素在数组右侧

1. 暴力解法：遍历整个数组，当首次遇到大于等于目标值的元素，就返回索引，此时就已经满足插入位置在数组左侧，在数组中间和数组中的元素三个条件，最后不满足上述遍历，就是插入位置在数组右侧的情况。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] >= target) {
                return i;
            }
        }
        return nums.size();

    }
};

2. 双指针：定义左右双指针，插入位置就是第一个大于等于目标值的元素，也就是right+1

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

    }
};

34.在排序数组中查找元素的第一个和最后一个位置

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

????????给你一个按照非递减顺序排列的整数数组?nums，和一个目标值?target。请你找出给定目标值在数组中的开始位置和结束位置。

????????如果数组中不存在目标值?target，返回?[-1, -1]。

????????你必须设计并实现时间复杂度为?O(log n)?的算法解决此问题。

????????本题的重点在于理解题意。查找元素的位置也就是以下三种情况:

(1) 查找的元素位置在数组的最左边或者最右边

(2) 查找元素在数组内部，但是找不到该元素

(3) 查找元素就是数组的内部元素

双指针：定义查找左右边界函数，定义默认左右边界，然后利用双指针来查找边界

Note：查找数组中的元素利用双指针法的时候，对于左右边界都必须是>= 或者 <= 才可以进行赋值，因为只有=才是真正找到了元素。同样重要的是理清楚本题的查找情况！

class Solution {
private:
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2;
        while(left <= right) {
            int middle = left + (right - left) / 2;
            if(nums[middle] >= target) {
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }
    int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2;
        while(left <= right) {
            int middle = left + (right - left) / 2;
            if(nums[middle] > target) {
                right = middle - 1;
            } else {
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 插入位置的元素在数组左侧或者右侧
        if(leftBorder == -2 || rightBorder == -2) return {-1, -1};
        // 查找元素是数组内部元素
        if(rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
        // 插入元素在数组内部且找不到
        return {-1, -1};
    }
};

感谢卡哥，感谢代码随想录！继续进步，加油！

代码随想录