LeetCode —— 数组

一、二分查找

定义 target 是在一个在左闭右开的区间里：

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
• if(nums[middle] > target) right 更新为middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else { // nums[mid] > target
                right = mid;
            }
        }
        // 未找到目标值
        return -1;
    }
}

提示：以下是本篇文章正文内容，下面案例可供参考

二、27. 移除元素

双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针：

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            if(nums[left] == val){
                nums[left] = nums[right];
                right--;
            }else {
                // 这里兼容了right指针指向的值与val相等的情况
                left++;
            }
        }
        return left;
    }
}

三、977.有序数组的平方

双指针法

• 数组其实是有序的， 只不过负数平方之后可能成为最大数了。
• 那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
• 此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
• 定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] result = new int[nums.length];
        // 新数组的指针，从大到小填数据
        int index = nums.length - 1;

        // 双指针思想
        while(left <=  right){
            if(nums[left] * nums[left] < nums[right] * nums[right]){
                result[index--] = nums[right] * nums[right];
                right--;
            } else {
                result[index--] = nums[left] * nums[left];
                left++;
            }
        }
        return result;
    }
}

四、209. 长度最小的子数组

滑动窗口

• 如果只用一个for循环来表示滑动窗口的起始位置，那么如何遍历剩下的终止位置？此时难免再次陷入 暴力解法的怪圈。所以 只用一个for循环，那么这个循环的索引，一定是表示滑动窗口的终止位置。
• 在本题中实现滑动窗口，主要确定如下三点：
• 窗口内是什么？ 如何移动窗口的起始位置？ 如何移动窗口的结束位置？
• 窗口就是满足其和 ≥ s 的长度最小的连续子数组。
• 窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。
• 窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 1. 初始化起始位置，数组和, 最终数组长度
        int i = 0, sum = 0, result = Integer.MAX_VALUE;
        // 2. 确定起始位置
        for(int j = 0; j <= nums.length - 1; j++){
            sum += nums[j];
            while(sum >= target){
                result = Math.min(result, j - i + 1);
                sum = sum - nums[i];
                i++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

五、59. 螺旋矩阵Ⅱ

循环不变量原则

• 模拟顺时针画矩阵的过程（左闭右开）:
• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0; //每圈起点
        int offset = 1;
        int count = 1;  //矩阵中要填写的数字
        int loop = 1;   //记录当前的圈数
        int i,j;    //j代表列，i代表行

        while(loop <= n / 2){

            //顶部
            //左闭右开，所以判断循环结束时，j不能等于n-offset
            for(j = startY; j < n - offset; j++){
                nums[startX][j] = count++;
            }

            //右列
            //左闭右开，所以判断循环结束时，i不能等于n-offset
            for(i = startX; i < n - offset; i++){
                nums[i][j] = count++;
            }

            //底部
            //左闭右开，所以判断循环结束时，j != startY
            for(; j > startY; j--){
                nums[i][j] = count++;
            }

            //左列
            //左闭右开，所以判断循环结束时，i != startX
            for(; i > startX; i--){
                nums[i][j] = count++;
            }

            startX++;
            startY++;
            offset++;
            loop++;
        }

        if(n % 2 == 1){
            nums[startX][startY] = count;
        }
        return nums;

    }
}