数组——算法专项刷题（二）

二、数组

数组题目中常用算法及思想：滑动窗口、双指针、前缀和。
注意点： 边界处理、辅助数据结构去重

2.1数组中和为3的个数

原题链接

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

思路： 双指针+两次去重 第二次去重 要在找到符合条件之后再去重，注意数组边界

 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;

        }
    }
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

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
2
3

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

思路： 滑动窗口， 右指针一直向右移动，记录窗口中的元素和 >= target 更新min最小值 左指针右移

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;
          

    }
}
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

时间复杂度 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 * 104
• 1 <= nums[i] <= 1000
• 0 <= k <= 106

思路： 滑动窗口，右指针右移 记录窗口中 元素乘积的个数 ，窗口中每增加一个数，总个数增加窗口总数个数

（比如：1，2，3，4 增加一个数 7 那么总数增加 5个 12347 2347 347 47 7） 窗口中元素乘积 >= k那么 右移左指针 并除去 左指针的值

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;

    }
}
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

2.4左右两边子数组的和

原题链接

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 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 即是所求

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;


    }
}
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

2.5 0和1个数相同的子数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1：

• 输入: nums = [0,1]
• 输出: 2
• 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1

思路： 将 0 变成 -1 ，使用map记录 前缀和 - > 下标，相同前缀和只记录最小下标，每遍历一个元素就 用 当前 前缀和 去前面 已经统计的前缀和中找到一个使得两者之间区间为0的下标 计算 区间长度

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;

    }
}
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

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.length
• n == matrix[i].length
• 1 <= m, n <= 200
• -10^5 <= matrix[i][j] <= 10^5
• 0 <= row1 <= row2 < m
• 0 <= 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

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];
    }
}
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

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集合保存 前缀和 -> 出现次数

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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.8长度为k子数组中最大和

原题链接

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：

• 子数组的长度是 k，且

• 子数组中的所有元素 各不相同 。

返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 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个元素没有重复的

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;
    }
}
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