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

た入场券 2024-04-01 15:21 75阅读 0赞

### 二、数组 ###

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

#### 2.1数组中和为3的个数 ####

[原题链接][Link 1]

> 给你一个整数数组 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;
    
            }
        }

#### 2.2和大于等于target的最短子数组 ####

[原题链接][Link 2]

给定一个含有 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 <= 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;
              
    
        }
    }

*时间复杂度 O(n) 空间复杂度O(1)*

#### 2.3乘积小于k的子数组 ####

[原题链接][Link 3]

给定一个正整数数组 `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;
    
        }
    }

#### 2.4左右两边子数组的和 ####

[原题链接][Link 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;
    
    
        }
    }

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

#### 2.6 二维子矩阵和 ####

[原题链接][Link 5]

给定一个二维矩阵 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：**

![在这里插入图片描述][364eb4da13d249f2b03e18c2ebe04cf3.png]

**输入:**

*  `["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];
        }
    }

#### 2.7 和为k的子数组 ####

[原题链接][Link 6]

给定一个整数数组和一个整数 `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;
    }
    }

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

[原题链接][Link 7]

给你一个整数数组 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/1fGaJU/
[Link 2]: https://leetcode.cn/problems/2VG8Kg/?envType=study-plan&id=lcof-ii&plan=lcof&plan_progress=4kehfu1
[Link 3]: https://leetcode.cn/problems/ZVAVXX/
[Link 4]: https://leetcode.cn/problems/tvdfij/
[Link 5]: https://leetcode.cn/problems/O4NDxx/
[364eb4da13d249f2b03e18c2ebe04cf3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0f2e6722324d4093a9dafbfe543e56dd.png
[Link 6]: https://leetcode.cn/problems/QTMn0o/
[Link 7]: https://leetcode.cn/problems/maximum-sum-of-distinct-subarrays-with-length-k/