代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素、977.有序数组的平方。

704.二分查找

总结：
防止int溢出：

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

(right - left) / 2 + left 是一种常见的技巧，确保计算数组中间索引时不会因为加法导致整数溢出，特别是在处理非常大的数组边界时非常有用。

27.移除元素

总结：使用快慢指针

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

使用快慢指针，快指针获得当下不等于val的值，并将其值赋给慢指针。

977.有序数组的平方

总结：使用双向指针

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int j=nums.size()-1;
        int k=nums.size()-1;
        vector<int> newQ(nums.size());
        for(int i=0;i<=j;){
            if(nums[i]*nums[i]>nums[j]*nums[j]){
                newQ[k--]=nums[i]*nums[i];
                i++;
            }
            else{
                newQ[k--]=nums[j]*nums[j];
                j--;
            }
        }
        return newQ;
    }
};

注意vector记得初始化，否则为0；