数组的再学习

一、数组的理论基础

1、数组是存放在内存空间上的相同类型数据的集合；
即：

• 数组内存空间的地址是连续的
• 数组下标都是从0开始的
  2、删除数组元素需要把该元素后面的元素整体向前移

3、二维数组的形式

二、二分查找

使用前提

• 有序数组
• 数组内无重复元素
  注意
• 需要注意while (left <= right)的临界值
• 数组的临界值

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) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三、移除元素

双指针

慢指针是新数组下标位置的指针
快指针是在旧数组中寻找新数组下标的指针

class Solution {
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

四、有序数组的平方

思路：创建一个新数组，在旧数组开头和结尾使用双指针，比较谁的平方大，谁就先放新数组中

class Solution {

    public int[] sortedSquares(int[] nums) {
        int len = nums.length;
        int[] numss = new int[len];
        int left = 0;
        int right = len -1;
        int index = len -1;
        while(left<=right){
            if(nums[left]*nums[left]<=nums[right]*nums[right]){
                numss[index--] = nums[right]*nums[right];
                right--;
            }else{
                numss[index--] = nums[left]*nums[left];

                left++;
            }
        }
        return numss;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

五、滑动窗口

即滑动的窗口，窗口内是满足条件的连续子数组
起始位置：当前窗口的值大于了目标值，窗口位置前移
结束位置：for遍历数组的指针

class Solution {

    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int left = 0;
        int res = Integer.MAX_VALUE;
        for(int right = 0;right<nums.length;right++){
            sum+=nums[right];
            while(sum>=target){
                res = Math.min(res,right-left+1);
                sum -= nums[left++];
            }
        }
        return res==Integer.MAX_VALUE?0:res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

六、螺旋矩阵II

思路：每次添加都左闭右开

class Solution {

    public int[][] generateMatrix(int n) {

        int loop = 0;
        int[][] res = new int[n][n];
        int start = 0;
        int index = 1;
        int i,j;

        while(loop++ < n/2){
                for(i=start;i<n-loop;i++){
                    res[start][i] = index++;
                }
                for(j = start;j<n-loop;j++){
                    res[j][i] = index++;
                }
                for(;i>=loop;i--){
                    res[j][i] = index++;
                }
                for(;j>=loop;j--){
                    res[j][i] = index++;
                }
            start++;
        }
        if(n%2 == 1){
            res[start][start] = index;
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31