977.有序数组的平方

题目建议： 本题关键在于理解双指针思想
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep

今天开始，尝试想象边做题边讲解，模拟面试的时候。

class Solution {
    public int[] sortedSquares(int[] nums) {
        // solution1: brute force
        // square each element and then sort the array
        // solution2:
        // Because 1. the array is sorted; 
        // 2. the largest number after squaring cannot be in the middle, use the two-pointer method
        // Create a new array of the same size as the original array
        int[] result = new int[nums.length];
        // The left pointer points to the start of the array, the right pointer points to the end of the array, and pointer k points to the end of the result array
        int left = 0;
        int right = nums.length - 1;
        int k = result.length - 1;
        
        while (left <= right) {
            // When nums[left]*nums[left] >  nums[right]*nums[right], fill the square of nums[left] into the end of the result array, move pointer k to the left, and move pointer left to the right
            // When nums[left]*nums[left] <  nums[right]*nums[right], fill the square of nums[right] into the end of the result array, move pointer k to the left, and move pointer right to the left
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                result[k] = nums[left] * nums[left];
                k--;
                left++;
            } else {
                result[k] = nums[right] * nums[right];
                k--;
                right--;
            }
        }
       
        // Return the result array
        return result;
    }
}

209.长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE

滑动窗口寻找最短

• 不满足条件时，扩展右边界；满足条件时，扩展左边界

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // Sliding window:
        // Condition: The problem requires a contiguous subarray
        // 1. Initialize variables and pointers
        int left = 0;
        int sum = 0;
        int sublength = Integer.MAX_VALUE; // Initialize the minimum subarray length to ensure it gets updated correctly later

        // 2. Determine the right boundary, expand the right boundary when the condition is not met
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            // 3. Slide the window, shrink the left boundary to update the minimum value when the condition is met
            while (sum >= target) {
                sublength = Math.min(sublength, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
      
        // 4. Return the result, if sublength == Integer.MAX_VALUE, it means it has not been updated, return 0
        return sublength == Integer.MAX_VALUE ? 0 : sublength;
    }
}

发现自己写的时候，想不到
int sublength = Integer.MAX_VALUE; //初始化最小子数组长度，确保之后可以正确更新
也想不到
sublength = Math.min(sublength, right-left+1);
对能直接调用的函数不太熟

59.螺旋矩阵II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

非常好题目，使我的大脑旋转。

第一次做，无从下手，看了解析再写的，重点还是循环不变量。感觉solution有点臃肿。准备明天再复习写一次。
在下班前还没搓完，今日上班摸鱼目标未达成。

class Solution {
    public int[][] generateMatrix(int n) {
        // 1. Initialization
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0; // Starting position for each layer of the spiral
        int count = 1; // Number to fill
        int offset = 1; // Used to control the length of each side, shrinking the right boundary by 1 each loop
        int mid = n / 2; // Position of the center of the matrix, used to handle odd numbers separately
        int loop = 1; // Record the number of loops
        int i, j; // Coordinates [i, j] of the matrix
        while (loop <= n / 2) { // Number of loops: each inner layer has a side length reduced by 2 compared to the outer layer
            i = startX;
            j = startY;
            // Top side
            for (; j < n - offset; j++) {
                nums[i][j] = count++;
            }
            // Right side
            for (; i < n - offset; i++) {
                nums[i][j] = count++;
            }
            // Bottom side
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }
            // Left side
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }
            startX++;
            startY++;
            offset++;
            loop++;
        }
        // Handle the center value of the matrix separately when n is odd
        if (n % 2 == 1) {
            nums[mid][mid] = count;
        }
       
        return nums;
    }
}

总结数组专题

二分查找:

• 性能:
  暴力解法: O(n)
  二分查找: O(logn)
• 注意: 维持循环不变量原则

双指针:

变体:
快慢指针（删除元素，处理重复元素）。

• 性能:
  暴力解法: O(n^2)
  双指针: O(n)
• 应用: 常用于数组和链表问题中以优化时间复杂度。移除元素。此外注意，数组中不能单独删除某一个元素

滑动窗口:

• 性能:
  暴力解法: O(n^2)
  滑动窗口: O(n)
• 应用: 适用于涉及子数组和动态子数组长度的问题。
• 关键：
  常见的题目关键词：寻找符合某些条件连续的子串
  • 寻找最短：
    如果窗口满足条件，L向右滑动扩大窗口，更新最优值；
    如果窗口不满足条件，R向右缩小窗口。
  • 寻找最长：
    如果窗口满足条件，R向右滑动扩大窗口，更新最优值；
    如果窗口不满足条件，L向右缩小窗口。

模拟行为:

比如 螺旋矩阵
注意: 循环不变量原则确保模拟过程中的一致性。
性能: 依问题而定，但通常为线性复杂度。