数组篇

二刷开始，从数组学起

1.二分查找

704. 二分查找

二分法很简单，通过一个left指针和right指针，确定mid = (left + right)/2，
当数组中 nums[mid] > target，说明targe在后半段，left = mid + 1；
当数组中 nums[mid] < target，说明targe在前半段，right = mid - 1；
最后左指针超过右指针时，说明数组中不存在target。
⚠️数组要求有序

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

2.移除元素

27. 移除元素

双指针：利用快慢指针 slow、fast，如果fast对应的数字不需被删去，则nums[slow] = nums[fast] 覆盖；若需要被删去则不做处理，fast++。
最终返回slow即数组[0, slow]为所求数组。

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if(nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}