数组（基于代码随想录）的随笔

数组

数组基础知识

数组是存放在连续内存空间上的相同类型数据的集合。

数组的元素是不能删的，只能覆盖。

那么二维数组在内存的空间地址是连续的么？

Java的二维数组在内存中不是 3*4 的连续地址空间，而是四条连续的地址空间组成！

数组的经典题目

• 二分法

二分法时间复杂度：O(logn)

循环不变量原则，只有在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。（这里选择左闭右闭（0 到 n-1））

low = 0 high = n-1 while(low<=high)

• 双指针

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

• 滑动窗口

滑动窗口时间复杂度：O(n)

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

对于leetcode中这题 https://leetcode.cn/problems/minimum-size-subarray-sum/

i 为滑动窗口的左边 ， j为滑动窗口的右边 ， sum为滑动窗口内总和大小

当sum小于目标值， j就右移

当sum大于目标值， i就右移

• 模拟行为

对于leetcode 中这题 https://leetcode.cn/problems/spiral-matrix-ii/

通过direct来表示移动的四个方向，通过index来改变方向。

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int k = 1;
        int i = 0;
        int j = 0;
        int[][] direct = {{0,1}, {1,0}, {0,-1}, {-1, 0}};
        int index = 0;
        while(k <=n * n){
            matrix[i][j] = k++;
            int direct1 = i + direct[index][0];
            int direct2 = j + direct[index][1];
            if(direct1<0 || direct1>=n ||direct2<0 || direct2>=n || matrix[direct1][direct2] != 0){
                index = (index + 1) % 4;
            }
            i = i + direct[index][0];
            j = j + direct[index][1];
        }
        return matrix;
    }
}

总结