专题：数组（已完结）

1.二分查找
有两种写法
第一种：左闭右闭
第二种：左闭右开
两种方法注意初始化 right的不同 以及更新right的不同

第一种：

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)/2;
            if(target>nums[mid]){
                left=mid+1;
            }else  if(target<nums[mid]){
               right=mid-1;;
            }else{
                return mid;
            }

        }
        return -1;
    }
};

第二种：

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

        }
        return -1;
    }
};

2.移除元素

这里用快慢指针
slowindex 指向将要填的位置

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowindex =0;
        int fastindex =0;
        for(int fastindex =0;fastindex<nums.size();fastindex++){
           if(nums[fastindex]!=val){
             nums[slowindex] = nums[fastindex];
             slowindex++;
           }
        }
        return slowindex;
    }
};

3.有序数组的平方
用双指针 i,j i指向头 j指向尾 平方后比较大小 大的直接放到新的数组中 新数组从尾部开始放

        int i=0;
        int j=nums.size()-1;

完整代码

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);
        while(i<=j){
            if(pow(nums[i],2) >pow(nums[j],2) ){
                result[k] = nums[i]*nums[i];
                k--;
                i++;
            }else{
                result[k] = nums[j]*nums[j];
                k--;
                j--; 
            }
        }
        return result;
    }
};

4.长度最小的子数组
需要
使用双指针法 j指针遍历数组nums[i] j管理右边界 每次遍历都加一，low管理左边界 左边界需要判断sum是否符合条件 因此左边界可能不止加一。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    int i=0;
    int sum = 0;
    int minlen =INT_MAX;
    for(int j=0;j<nums.size();j++){
      sum=sum+nums[j];
      while(sum>=target){
        minlen=min(minlen,j-i+1);
        sum=sum-nums[i];
        i++;
      }
    }
    return minlen==INT_MAX? 0:minlen;
    }
};

5.螺旋矩阵II
略

原文地址：https://blog.csdn.net/qq_23923713/article/details/142941114

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！