前缀和差分数组编程题集合

太过爱你忘了你带给我的痛 2023-09-25 22:08 11阅读 0赞

> 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
> 
> 示例 1：
> 
> 输入：nums = \[1,1,1\], k = 2  
> 输出：2  
> 示例 2：
> 
> 输入：nums = \[1,2,3\], k = 3  
> 输出：2
> 
> 来源：力扣（LeetCode）  
> 链接：https://leetcode.cn/problems/subarray-sum-equals-k

前缀和加哈希表优化，单纯的使用前缀和本题会超过时间限制，所以在前缀和的基础上加上哈希表进行优化。

public int subarraySum(int[] nums, int k) {
            int pre=0;
            int result=0;
            Map<Integer,Integer> map=new HashMap<>();
            map.put(0,1);
           for(int i=0;i<nums.length;i++){
              pre+=nums[i];
              if(map.containsKey(pre-k))
                  result+=map.get(pre-k);
              map.put(pre,map.getOrDefault(pre,0)+1);
    
           }
           return result;
        }

滑动窗口，本题我也考虑过使用滑动窗口，但是提交的时候发现很多的问题，对于类似的题数组的值必须是全是正数或负数的可以使用滑动窗口，既有正数也有负数的此类题目并不适用滑动窗口。

下面是动态规划解法，但是数据量很大的时候就会时间超时。代码如下

//dp[i][j]表示数组中i索引到j的元素的和
        public int subarraySum(int[] nums, int k) {
            int dp[][]=new int[nums.length][nums.length];
            int result=0;
            for(int i=0;i<nums.length;i++){
                for(int j=i;j<nums.length;j++){
                    if(i==j)
                    dp[i][i]=nums[i];
                    else
                    dp[i][j]=dp[i][j-1]+nums[j];
                    if(dp[i][j]==k)
                        result++;
                }
            }
            return result;
    
    
        }

> 给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
> 
> 子数组大小 至少为 2 ，且  
> 子数组元素总和为 k 的倍数。  
> 如果存在，返回 true ；否则，返回 false 。
> 
> 如果存在一个整数 n ，令整数 x 符合 x = n \* k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。
> 
> 示例 1：
> 
> 输入：nums = \[23,2,4,6,7\], k = 6  
> 输出：true  
> 解释：\[2,4\] 是一个大小为 2 的子数组，并且和为 6 。  
> 示例 2：
> 
> 输入：nums = \[23,2,6,4,7\], k = 6  
> 输出：true  
> 解释：\[23, 2, 6, 4, 7\] 是大小为 5 的子数组，并且和为 42 。  
> 42 是 6 的倍数，因为 42 = 7 \* 6 且 7 是一个整数。  
> 示例 3：
> 
> 输入：nums = \[23,2,6,4,7\], k = 13  
> 输出：false

public static boolean checkSubarraySum(int[] nums, int k) {
            int pre=0;
            if(nums.length<2)
                return false;
            Map<Integer,Integer> map=new HashMap<>();
            map.put(0,-1);
            for(int i=0;i<nums.length;i++){
                pre+=nums[i];
                if(map.containsKey(pre%k)){
                  if(i-map.get(pre%k)>=2){
                      return true;
                  }
                }
                else
                map.put(pre%k,i);
            }
            return false;
        }

> 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
> 
> 示例 1:
> 
> 输入: nums = \[0,1\]  
> 输出: 2  
> 说明: \[0, 1\] 是具有相同数量 0 和 1 的最长连续子数组。  
> 示例 2:
> 
> 输入: nums = \[0,1,0\]  
> 输出: 2  
> 说明: \[0, 1\] (或 \[1, 0\]) 是具有相同数量0和1的最长连续子数组。

public static int findMaxLength(int[] nums) {
    		 	if(nums.length<2)
    		 		return 0;
    		 int pre=0;
    		 int max=0;
    		 Map<Integer, Integer> map=new HashMap<>();
    		 map.put(0, -1);
    		 for(int i=0;i<nums.length;i++) {
    			 if(nums[i]==0)
    				 pre=pre-1;
    			 else
    			     pre=pre+nums[i];
    			 if(map.containsKey(pre)) {
    				 max=Math.max(max, i-map.get(pre));
    			 }
    			 else {
    				 map.put(pre, i);
    			 }
    		 }
    		 return max;
    		 	
    	    }

> 给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空） 子数组 的数目。
> 
> 子数组 是数组的 连续 部分。
> 
> 示例 1：
> 
> 输入：nums = \[4,5,0,-2,-3,1\], k = 5  
> 输出：7  
> 解释：  
> 有 7 个子数组满足其元素之和可被 k = 5 整除：  
> \[4, 5, 0, -2, -3, 1\], \[5\], \[5, 0\], \[5, 0, -2, -3\], \[0\], \[0, -2, -3\], \[-2, -3\]  
> 示例 2:
> 
> 输入: nums = \[5\], k = 9  
> 输出: 0

public int subarraysDivByK(int[] nums, int k) {
              int pre=0;   
            Map<Integer,Integer> map=new HashMap<>();
            map.put(0,1);
            int result=0;
            for(int i=0;i<nums.length;i++){
                pre+=nums[i];
                int key=(pre%k+k)%k;
                if(map.containsKey(key)){
                  result+=map.get(key);
                }
                map.put(key,map.getOrDefault(key, 0)+1);
            }
            return result;
        }

> #### 差分数组： ####
> 
> 对于数组a\[i\]，我们令d\[i\]=a\[i\]-a\[i-1\] (特殊的，第一个为d\[1\]=a\[1\])，则d\[i\]为一个差分数组。
> 
> 我们发现统计d数组的前缀和sum数组，有
> 
> sum\[i\]=d\[1\]+d\[2\]+d\[3\]+...+d\[i\]=a\[1\]+a\[2\]-a\[1\]+a\[3\]-a\[2\]+...+a\[i\]-a\[i-1\]=a\[i\],即**前缀和sum\[i\]=a\[i\]；**
> 
> 因此每次在区间\[l,r\]增减x只需要令d\[l\]+x,d\[r+1\]-x，就可以保证\[l,r\]增加了x，而对\[1,l-1\]和\[r+1,n\]无影响。 复杂度则是O(n)的

> [1109. 航班预订统计][1109.]
> 
> 难度中等453收藏分享切换为英文接收动态反馈
> 
> 这里有 `n` 个航班，它们分别从 `1` 到 `n` 进行编号。
> 
> 有一份航班预订表 `bookings` ，表中第 `i` 条预订记录 `bookings[i] = [firsti, lasti, seatsi]` 意味着在从 `firsti` 到 `lasti` （**包含** `firsti` 和 `lasti` ）的 **每个航班** 上预订了 `seatsi` 个座位。
> 
> 请你返回一个长度为 `n` 的数组 `answer`，里面的元素是每个航班预定的座位总数。
> 
> **示例 1：**
> 
>     输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
>     输出：[10,55,45,25,25]
>     解释：
>     航班编号        1   2   3   4   5
>     预订记录 1 ：   10  10
>     预订记录 2 ：       20  20
>     预订记录 3 ：       25  25  25  25
>     总座位数：      10  55  45  25  25
>     因此，answer = [10,55,45,25,25]

public  int[] corpFlightBookings(int[][] bookings, int n) {
    		 
    		 int arr[]=new int[n+2];
    		 for(int i=0;i<bookings.length;i++) {
    			 int m=bookings[i][0];
    			 int nn=bookings[i][1];
    			 int x=bookings[i][2];
    			 arr[m]+=x;
    			 arr[nn+1]-=x;
    		 }
        
    		 int sum[]=new int[n];
    		 sum[0]=arr[1];
    		 for(int i=1;i<n;i++)
    			 sum[i]=sum[i-1]+arr[i+1];
    		 return sum;
    	 }

[1109.]: https://leetcode.cn/problems/corporate-flight-bookings/