二、数组
数组题目中常用算法及思想：滑动窗口、双指针、前缀和。
注意点： 边界处理、辅助数据结构去重
2.1数组中和为3的个数
原题链接
给你一个整数数组 nums ，判断是否存在三元组
[nums[i], nums[j], nums[k]]满足i != j、i != k 且 j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请
你返回所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
思路： 双指针+两次去重 第二次去重 要在找到符合条件之后再去重，注意数组边界
java"> class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n-2; i++) {
//去重
if(i >0 && nums[i] == nums[i-1]) continue;
int l = i+1, r = n-1;
while(l < r){
int num = nums[i] + nums[l] + nums[r];
if(num > 0){
r--;
}else if(num < 0){
l++;
}else{
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[l]);
list.add(nums[r]);
res.add(list);
l++;
//第二次去重
while(l < r && nums[l] == nums[l-1]) l++;
}
}
}
return res;
}
}
2.2和大于等于target的最短子数组
原题链接
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
提示：
1 <= target <= 1091 <= nums.length <= 1051 <= nums[i] <= 105
思路： 滑动窗口， 右指针一直向右移动，记录窗口中的元素和 >= target 更新min最小值 左指针右移
java">class Solution {
public int minSubArrayLen(int target, int[] nums) {
int len = nums.length;
int l = 0;
int min = len+1;
int sum = 0;
for(int r = 0; r < len; r++){
sum += nums[r];
while(sum >= target){
min = Math.min(min, r - l + 1);
//减去左边的值
sum -= nums[l];
l++;
}
}
// 如果min还等于len+1 说明没有符合条件的
return min == len+1 ? 0 : min;
}
}
时间复杂度 O(n) 空间复杂度O(1)
2.3乘积小于k的子数组
原题链接
给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:
-
输入: nums = [10,5,2,6], k = 100
-
输出: 8
-
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
-
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
提示:
1 <= nums.length <= 3 * 1041 <= nums[i] <= 10000 <= k <= 106
思路： 滑动窗口，右指针右移 记录窗口中 元素乘积的个数 ，窗口中每增加一个数，总个数增加窗口总数个数
（比如：1，2，3，4 增加一个数 7 那么总数增加 5个 12347 2347 347 47 7） 窗口中元素乘积 >= k那么 右移左指针 并除去 左指针的值
java">class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int n = nums.length;
int l = 0, r = 0, num = 1, res = 0;
while(r < n){
num *= nums[r];
// 左指针右移 注意 左指针不能大于右指针
while(num >= k && l <= r){
num /= nums[l];
l++;
}
// 窗口中每增加一个数，总个数增加窗口总数个数
res += r- l +1;
r++;
}
return res;
}
}
2.4左右两边子数组的和
原题链接
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1：
输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
提示：
1 <= nums.length <= 104-1000 <= nums[i] <= 1000
思路： 两次遍历数组，第一次求数组元素和sum，第二次求遍历到的元素之前的和res，并不断用sum 减去 遍历过的元素 如果sum = res 即是所求
java">class Solution {
public int pivotIndex(int[] nums) {
int sum = 0;
int n = nums.length;
for(int i = 0; i < n;i++){
sum += nums[i];
}
int res = 0;
for(int i = 0; i < n;i++){
sum -= nums[i];
if(sum == res) return i;
res += nums[i];
}
return -1;
}
}
2.5 0和1个数相同的子数组
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1：
- 输入: nums = [0,1]
- 输出: 2
- 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
提示：
1 <= nums.length <= 105nums[i]不是0就是1
思路： 将 0 变成 -1 ，使用map记录 前缀和 - > 下标，相同前缀和只记录最小下标，每遍历一个元素就 用 当前 前缀和 去前面 已经统计的前缀和中找到一个使得两者之间区间为0的下标 计算 区间长度
java">class Solution {
public int findMaxLength(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if(nums[i] == 0){
nums[i] = -1;
}
}
int res = 0;
HashMap<Integer,Integer> map = new HashMap();
// 处理边界
map.put(0,-1);
//记录前缀和
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
//如果前面存在前缀和相同的 求区间长度
if(map.containsKey(sum)){
res = Math.max(res,i-map.get(sum));
}else{
map.put(sum,i);
}
}
return res;
}
}
2.6 二维子矩阵和
原题链接
给定一个二维矩阵 matrix，以下类型的多个请求：
- 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix)给定整数矩阵 matrix 进行初始化int sumRegion(int row1, int col1, int row2, int col2)返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。
示例1：
输入:
["NumMatrix","sumRegion","sumRegion","sumRegion"][[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出:
- [null, 8, 11, 12]
解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]]);numMatrix.sumRegion(2, 1, 4, 3);// return 8 (红色矩形框的元素总和)numMatrix.sumRegion(1, 1, 2, 2);// return 11 (绿色矩形框的元素总和)numMatrix.sumRegion(1, 2, 2, 4);// return 12 (蓝色矩形框的元素总和)
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 200-10^5 <= matrix[i][j] <= 10^50 <= row1 <= row2 < m0 <= col1 <= col2 < n- 最多调用 10^4 次 sumRegion 方法
思路： 使用前缀和思想，两个点 (x1, y1) , (x2, y2 )组成的子矩阵的和等于 (x2, y2) - (x2, y1 ) -(x1, y2) + (x1, y1)
注意点： 求数组前缀和时，使用count记录每行的前缀和 ,res[i+1][j+1] = res[i][j+1] + count
java">class NumMatrix {
int[][] res;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
res = new int[m+1][n+1];
for(int i = 0; i < m;i++){
//记录每行前缀和
int count = 0;
for(int j = 0; j < n;j++){
count += matrix[i][j];
res[i+1][j+1] = res[i][j+1] + count;
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return res[row2+1][col2+1] - res[row1][col2+1] - res[row2+1][col1] + res[row1][col1];
}
}
2.7 和为k的子数组
原题链接
给定一个整数数组和一个整数 k ， 请找到该数组中和为 k 的连续子数组的个数。
示例 1：
- 输入:nums = [1,1,1], k = 2
- 输出: 2
- 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
提示:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
思路： 前缀和思想，使用map集合保存 前缀和 -> 出现次数
java">class Solution{
public int subarraySum(int[] nums, int k) {
// 前缀 -> 出现次数
Map<Integer, Integer> map = new HashMap<>();
// 以防nums[0]就是k
map.put(0, 1);
int pre = 0, cnt = 0;
for (int num : nums) {
pre += num;
// 已知当前的前缀pre和之前某个前缀X，且要求pre-X=k，那么X=pre-k。X的出现次数就是此时以num结尾的子数组的次数
cnt += map.getOrDefault(pre - k, 0);
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return cnt;
}
}
2.8长度为k子数组中最大和
原题链接
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
示例 1：
输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：nums 中长度为 3 的子数组是：
- [1,5,4] 满足全部条件，和为 10 。
- [5,4,2] 满足全部条件，和为 11 。
- [4,2,9] 满足全部条件，和为 15 。
- [2,9,9] 不满足全部条件，因为元素 9 出现重复。
- [9,9,9] 不满足全部条件，因为元素 9 出现重复。
因为 15 是满足全部条件的所有子数组中的最大子数组和，所以返回 15 。
思路： 固定窗口+map，求连续等长度的子数组，使用固定长度的滑动窗口。使用map记录窗口中的元素及个数用于检查是否重复。如果map
注意点： 判断前k个元素时，使用map的大小与k作比较，如果相等就说明前k个元素没有重复的
java">class Solution {
public long maximumSubarraySum(int[] nums, int k) {
long max = 0;
int n = nums.length ;
long sum =0;
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < k; i++) {
sum += nums[i];
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
//说明前 k 的元素没有重复的
if(map.size() == k) {
max = Math.max(max, sum);
}
for (int i = k; i < n ; i++) {
//右指针右移
sum += nums[i];
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
sum -= nums[i - k];
//获取map中 左窗口的元素个数
int cnt = map.get(nums[i - k]);
//如果只出现一次 直接移除
if(cnt == 1){
map.remove(nums[i-k]);
}else {
//出现多次 次数 -1
map.put(nums[i-k],cnt-1);
}
if(map.size() == k)
max = Math.max(max, sum);
}
return max;
}
}
