数组 level 1

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算！
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1); //右移一位就是除2
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else return mid;
        }
        return -1;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // 定义target在左闭右开的区间里，所以右边的开边界不用减一
        while(left < right){
            int mid = left + (right-left)/2;
            if (nums[mid] < target){
                left = mid +1;
            }
            else if (nums[mid] > target){
                right = mid ;
            }
            else return mid;
        }
        return -1;
    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int fastIndex = 0;
        int slowIndex;
        for (slowIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;

    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
                //这里不能加left++;因为有可能nums[right - 1]也等于val，所以还得继续判断当前的left元素。
            } else {
                left++;
            }
        }
        return left;
    }
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        int[] res = new int[nums.length];
        int k = nums.length - 1;
        while(l <= r){
            if(nums[l] * nums[l] > nums[r] * nums[r]){
                res[k--] = nums[l] * nums[l++];
            }else{
                res[k--] = nums[r] * nums[r--];
            }
        }
        return res;
    }
}

class Solution {

    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int loop = n/2; // 循环几个圈
        int mid = n/2;
        int offset = 1;
        int count = 1;
        int startx = 0, starty = 0;
        
        while(loop>0){
            int x = startx, y = starty;
            for(;y < starty + n - offset; y++){
                res[startx][y] = count++;
            }
            for(;x < startx + n - offset; x++){
                res[x][y] = count++;
            }
            for(;y > starty; y--){
                res[x][y] = count++;
            }
            for(;x > startx; x--){
                res[x][y] = count++;
            }
            offset += 2; // offset 控制每一圈里每一条边遍历的长度
            startx++;
            starty++;
            loop--;
        }
        // 如果n为奇数的话，需要单独给矩阵最中间的位置赋值
        if (n % 2 == 1){
            res[mid][mid] = n*n;
        }
        return res;
    }
}