704. 二分查找

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

二分查找 用于有序数组中，没有重复的数组。首先需要定义一个头（left）和尾(right)，最后通过mid和target对比不断修改头和尾指向的位置。

【需要注意区间问题，根据区间的开和闭决定边界条件】

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

推荐练习 leetcode35. 

27.移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

这里其实有序无序都可以，正常的调用内置函数的复杂度是O（n），是用的两个for循环进行暴力解。这里要求我们原地执行，所以用一个for循环解决。

【这里我们要知道数组的删除，其实和我们平时理解的删除并不一样，数组的删除前其实是将不需要的元素进行覆盖，内存中他还是存在的】

这里用到了快慢指针，一个fast和一个slow，fast用于遍历整个数组，所以for循环的执行条件就应该是当fast小于数组长度的时候就进行一次循环，而slow指针怎么变化呢？如果nums[fast]不是需要的val，那就令nums[fast] = nums[slow]，当nums[fast] = val的时候，slow指针的位置不需要变，这样可以把slow看作一个新的数组，用于装不包含val值的数组，当nums[fast]再次不等于val的时候将nums[fast]再次赋给nums[slow]，slow指针再次向后移动。

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

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路和上一题类似，也是用双指针，这里两头的平方一定会大于中间的值的平方，所以新建立一个数组从后往前放置原数组的平方的值。

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int left = 0;int right = nums.size() - 1;int k = nums.size() - 1;   //因为数组的两头的数字的绝对值一定大于中间的，所以result数组从后往前放vector<int> result(nums.size(), 0);for(; left <= right;){if(nums[left] * nums[left] < nums[right] * nums[right]){   result[k--] = nums[right] * nums[right];right --;}else{result[k--] = nums[left] * nums[left];left ++;}}return result;}
};