理论基础

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

数组可以方便的通过下标索引的方式获取到下标对应的数据。

需要注意的是:

  • 数组下标都是从0开始的。
  • 数组内存空间的地址是连续的

正是因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作。

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

二维数组诸如 a[0][1]这样的，先行后列。

我们主要采用以下方法处理数组相关问题：

  • 二分法
  • 滑动窗口
  • 双指针
  • 模拟过程
  • 前缀和数组

二分查找

例题：[704. 二分查找]

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1

提示：

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间

思路

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。最关键的地方就是定义好每一个边界。

二分法经常写乱，主要是因为区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

有这些边界需要处理：

  • while 循环里，是(left< right) 还是 (left<= right)
  • nums[mid] > target时，right 是否是 mid-1 ？
  • nums[mid] < target时，left 是否是 mid+1 ？

定义一个在左闭右开的区间为例子，也就是[left, right)。

首先对于while循环，我们必须保证当前while的条件是合法的。因为left == right在区间[left, right)是没有意义的，这里使用 <。

其次，if (nums[mid] > target) right 应该更新为 mid。因为当前已经确认nums[mid]不等于target，要去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为mid。如果这里更新为mid-1，查询中会丢失nums[mid-1]。

其次，if (nums[mid]<target) left 应该更新为 mid+1。因为当前已经确认nums[mid]不等于target，要去右区间继续寻找，而寻找区间是左闭右开区间，如果这里更新为mid，查询中会多比较一次nums[mid]。

即：保证下一个查询区间不会去比较nums[mid]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid]>target){
                right = mid;
            }else if(nums[mid]<target){
                left = mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
}

左闭右闭同理，只是两次更新需要分别进行mid-1，mid+1的处理，这样才能保证不重复搜索边界上的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; 
            if (nums[mid] == target) {
                return mid;  
            }
            if (nums[mid] < target) {
                left = mid + 1; 
            } else {
                right = mid - 1;
            }
        }
        return -1;  
    }
}

相关题目

移除元素

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

你不需要考虑数组中超出新长度后面的元素。

思路

数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

暴力

两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0; // 用于追踪有效元素的数量
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];  
                k++; 
            }
        }
        return k;  
    }
}

双指针

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

定义快慢指针

  • 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
  • 慢指针：指向更新 新数组下标的位置，可以作为新数组长度的索引
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;
        for(int fast = 0; fast < nums.length ; fast++ ){
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

相关题目

有序数组的平方

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

  • 输入：nums = [-4,-1,0,3,10]
  • 输出：[0,1,9,16,100]
  • 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2：

  • 输入：nums = [-7,-3,2,3,11]
  • 输出：[4,9,9,49,121]

思路

暴力

每个数平方之后，排个序。

1
2
3
4
5
6
7
8
9
class Solution {
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

双指针

数组平方的最大值就在数组的两端，不是最左边就是最右边，反正绝对不可能是中间。

双指针一左一右，比较大小，把较大的填到答案数组里，然后移动指针。

最终循环次数达到nums.length-1，说明遍历结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] result = new int[nums.length];
        
        for (int index = nums.length - 1; index >= 0; index--) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[index] = nums[left] * nums[left++];
            } else {
                result[index] = nums[right] * nums[right--];
            }
        }
        return result;
    }
}

长度最小的子数组

209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

  • 输入：s = 7, nums = [2,3,1,2,4,3]
  • 输出：2
  • 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

思路

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, sum = 0;
        int len = nums.length+1;  

        while (right < nums.length) {
            sum += nums[right];  // 向右扩展窗口，更新 sum
            right++;  // 移动右指针

            // 当 sum >= target 时，尝试缩小窗口
            while (sum >= target) {
                len = Math.min(len, right - left);  // 记录最小子数组长度
                sum -= nums[left];  // 缩小窗口，减去左边界的值
                left++;  // 移动左指针
            }
        }

        return len == nums.length+1 ? 0 : len; 
    }
}

相关题目

螺旋矩阵II

[59. 螺旋矩阵 II]

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

img

输入: 3

输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

思路

这是一个典型的模拟过程题。

要写出正确的二分法一定要坚持循环不变量原则。而求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

保持一个不变，另一个变，就这样由外向内一圈一圈画下去。

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
32
33
34
35
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        int current = 1;
        
        // 四个边界 (left, right, top, bottom) 限制填充范围
        while (left <= right && top <= bottom) {

            for (int i = left; i <= right; i++) {
                nums[top][i] = current++;
            }top++; 
            
            for (int i = top; i <= bottom; i++) {
                nums[i][right] = current++;
            }right--; 
            
            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    nums[bottom][i] = current++;
                }bottom--; 
            }
            
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    nums[i][left] = current++;
                }left++; 
            }
        }
        
        return nums;
    }
}

类似题目

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// 54
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int n = matrix.length;
        if (n == 0) return result;  // 如果矩阵为空，直接返回空列表
        
        int m = matrix[0].length;  // 获取矩阵的列数
        
        int left = 0, right = m - 1, top = 0, bottom = n - 1;
        
        // 四个边界 (left, right, top, bottom) 限制填充范围
        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) {
                result.add(matrix[top][i]);
            }top++;

            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }right--;

            if (top <= bottom) {
                for (int i = right; i >= left; i--) {
                    result.add(matrix[bottom][i]);
                }bottom--;
            }
            
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }left++;
            }
        }

        return result;
    }
}



// LCR 146
    class Solution {
    public int[] spiralArray(int[][] array) {
        int n = array.length;
        if (n == 0) return new int[0];  // 处理空矩阵的情况

        int m = array[0].length; // 处理非方阵情况
        int[] nums = new int[n * m];
        
        int left = 0, right = m - 1, top = 0, bottom = n - 1;
        int current = 0;
        
        // 四个边界 (left, right, top, bottom) 限制填充范围
        while (left <= right && top <= bottom) {

            // 从左到右填充顶部
            for (int i = left; i <= right; i++) {
                nums[current++] = array[top][i];
            }
            top++; // 顶部边界向下移动

            // 从上到下填充右侧
            for (int i = top; i <= bottom; i++) {
                nums[current++] = array[i][right];
            }
            right--; // 右边界向左移动

            if (top <= bottom) {
                // 从右到左填充底部
                for (int i = right; i >= left; i--) {
                    nums[current++] = array[bottom][i];
                }
                bottom--; // 底部边界向上移动
            }

            if (left <= right) {
                // 从下到上填充左侧
                for (int i = bottom; i >= top; i--) {
                    nums[current++] = array[i][left];
                }
                left++; // 左边界向右移动
            }
        }
        
        return nums;
    }
}

接雨水

题目链接(opens new window)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

img

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

  • n == height.length
  • 1 <= n <= 2 * 104
  • 0 <= height[i] <= 105

思路

前缀和

首先对局部分析，一个格子里能接雨水的高度都取决于较短的邻边。如果雨水的高度超过了邻边的高度，它就会流出。

所以，在这个局部，最多能接的雨水量是：

最矮的邻边高度和这一格高度的差值。

推广到整体，任一处水的高度都绝对不会超过两侧最高的边里较低的那一个，否则它就会流出。

因此得出结论，一格里最多能接的雨水量是：两侧最高的边里更矮的那一个的高度和这一格高度的差值。

这里不用担心邻边不够高而导致水流出去，因为在整体满足这一条件的情况下，邻边的空位也一定会被水填满。

我们的思路是：使用两个数组，分别是前缀数组和后缀数组，储存各自某一位之前的最大值。

然后对height数组遍历，用前缀和后缀数组的最小值表示当前格左右两侧最高值中较小的那一个的值。接下来减去高度值，就是上文提及的差值。

最后将差值累加，遍历结束后输出结果。

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
32
33
34
35
36
37
38
39
40
public class Solution {
    // 返回较大的值
    private int max(int a, int b) {return a > b ? a : b;}

    // 返回较小的值
    private int min(int a, int b) {return a < b ? a : b;}

    public int trap(int[] height) {
        int heightSize = height.length;
        if (heightSize == 0) {return 0;}
        int ans = 0;

        // premax 数组保存左边每个位置的最大值
        int[] premax = new int[heightSize];
        // submax 数组保存右边每个位置的最大值
        int[] submax = new int[heightSize];

        // 初始化 premax 和 submax
        premax[0] = height[0];
        submax[heightSize - 1] = height[heightSize - 1];

        // 填充 premax 数组
        for (int i = 1; i < heightSize; i++) {
            premax[i] = max(premax[i - 1], height[i]);
        }

        // 填充 submax 数组
        for (int i = heightSize - 2; i >= 0; i--) {
            submax[i] = max(submax[i + 1], height[i]);
        }

        // 计算每个位置上能接的水
        for (int i = 0; i < heightSize; i++) {
            ans += min(submax[i], premax[i]) - height[i];
        }

        return ans;
    }
}

类似题目

11.盛最多水的容器