數(shù)組理論基礎(chǔ)

基本說明

Java數(shù)組的父類為Object，可以存儲的數(shù)據(jù)類型有：基本數(shù)據(jù)類型、引用數(shù)據(jù)類型（對象）。數(shù)組有定長特性，長度一經(jīng)定下不可修改。要求可變長度時可考慮集合等其他存儲結(jié)構(gòu)。它存儲在Java虛擬機(jī)的堆內(nèi)存中，用new來創(chuàng)建，是一串連續(xù)的內(nèi)存地址。由于元素類型相同，因此占用內(nèi)存空間一樣。占用的內(nèi)存大小已知，使得它可以根據(jù)起始位置與下標(biāo)直接找到數(shù)據(jù)地址，查詢快。如果在數(shù)組中增刪數(shù)據(jù)，增刪位置后面的數(shù)據(jù)都要向前或向后移動，增刪慢。

操作方式

靜態(tài)初始化（指定內(nèi)容，長度等于內(nèi)容個數(shù)）：int[] arr = new int[]{1,2,3,4,5};

動態(tài)初始化（指定長度，默認(rèn)初始值由數(shù)組的字符類型而定）：int arr[] = new int[3];

利用索引訪問，其數(shù)組范圍皆為從0到數(shù)組名.length-1。遍歷方式：for循環(huán)遍歷、for each遍歷（for增強(qiáng)）。兩者的區(qū)別是遍歷過程中的局部變量代表的含義，前者代表數(shù)組的元素下標(biāo)，后者代表數(shù)組的具體內(nèi)容。

常見API

Arrays.toString()：輸出字符串、Arrays.asList()：將數(shù)組轉(zhuǎn)為List、List.toArray()：將List轉(zhuǎn)為數(shù)組。

簡單題

[704]二分查找，[27]移除元素，[977]有序數(shù)組的平方。

都可使用雙指針法解決，不再贅述。

中等題

[209]長度最小的子數(shù)組

題設(shè)：給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。找出該數(shù)組中滿足其總和大于等于 target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度。如果不存在符合條件的子數(shù)組，返回 0 。

思路：卡哥把這種方法叫做滑動窗口法，其實(shí)就是通過雙指針的移動，確定子數(shù)組的開始與結(jié)束位置。如下圖：

209圖解.png

結(jié)束索引先開始移動，直至子數(shù)組和大于目標(biāo)值，再移動起始索引，直至子數(shù)組和小于目標(biāo)值，循環(huán)往復(fù)。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int start = 0;
        int length = Integer.MAX_VALUE;
        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];
            while (sum >= target) {
                length = Math.min(length, end - start + 1);
                sum -= nums[start++];
            }
        }
        return length == Integer.MAX_VALUE ? 0 : length;
    }
}

時間復(fù)雜度：O(n)，其中n是數(shù)組的長度。指針start和end最多各移動n次。

空間復(fù)雜度：O(1)。

[59]螺旋矩陣 II

題設(shè)：給你一個正整數(shù) n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。

思路：螺旋矩陣題需要考慮地比較細(xì)致，其核心為始終左閉右開。循環(huán)層數(shù)為矩陣行數(shù)/2，當(dāng)行數(shù)為奇數(shù)時，要對矩陣中心值進(jìn)行單獨(dú)賦值。在每層循環(huán)中，模擬從左到右、從上到下、從右到左、從下到上四個遍歷過程。

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int loop = 0;
        int num = 1;
        while (loop < n / 2) {
            //從左到右
            for (int i = loop; i < n - loop - 1; i++) {
                res[loop][i] = num++;
            }
            //從上到下
            for (int i = loop; i < n - loop - 1; i++) {
                res[i][n - loop - 1] = num++;
            }
            //從右到左
            for (int i = n - loop - 1; i > loop; i--) {
                res[n - loop - 1][i] = num++;
            }
            //從下到上
            for (int i = n - loop - 1; i > loop; i--) {
                res[i][loop] = num++;
            }
            loop++;
        }
        if (n % 2 == 1) res[loop][loop] = num;
        return res;
    }
}

其中，起始值、索引值邊界都可以用loop循環(huán)值來控制，只要堅(jiān)持左閉右開的原則，細(xì)心即可。

時間復(fù)雜度：O(n2)，其中n是給定的正整數(shù)。矩陣的大小是n×n，需要填入矩陣中的每個元素。

空間復(fù)雜度：O(1)。除了返回的矩陣以外，空間復(fù)雜度是常數(shù)。

總結(jié)

數(shù)組總結(jié).png