知识点

知识点
1. 前缀和解决子数组问题
  1. 问题描述
    
    给定一个数组和一个整数和k，算出一共有几个和为 k 的子数组
  2. 解题思路：
    
    思路很简单，我把所有子数组都穷举出来，算它们的和，看看谁的和等于 k 不就行了，但是，如何快速得到某个子数组的和呢，例如快速计算nums[i..j]的和。
    
    因此，上述的穷举思路就不可以了，必须使用一种技巧：前缀和技巧。
    
    前缀和技巧描述为：定义一个前缀和数组preSum[nums.length()+1]，该数组的定义为preSum[i]为nums[0..i-1]个元素的和，因此preSum叫做前缀和数组。有了preSum数组，要快速求nums[i..j]的和，只需要preSum[j+1]-preSum[i]即可。
    
    利用前缀和技巧，很容易可以得到一个新的前缀和解法：
```
 public int subarraySum(int[] nums, int k) {

 int res = 0;

 // 定义前缀和数组
 int[] preSum = new int[nums.length + 1];
 for(int i = 1; i <= nums.length; i++) {
     preSum[i] = nums[i - 1] + preSum[i - 1];
 }

 // 穷举所有的子数组
 for (int j = 0; j < nums.length; j++) {
     for (int i = j; i >= 0; i--) {
         if (preSum[j + 1] - preSum[i] == k) {
             res++;
         }
     }
 }

 return res;
}
```
    该前缀和解法时间复杂度O(N^2)空间复杂度O(N)，并不是最优的解法
    
    这个前缀和解法还可以优化，优化思路为：第二层 for 循环在干嘛呢？翻译一下就是，在计算，有几个j能够使得sum[i]和sum[j]的差为 k。毎找到一个这样的j，就把结果加一。如果我直接记录下有几个sum[j]和sum[i]-k相等，直接更新结果，就避免了内层的 for 循环。优化后代码如下：
```
 public int subarraySum(int[] nums, int k) {

int res = 0;

// 改用Hash表来作为前缀数组，Hash表定义为：前缀和->前缀和出现次数
HashMap<Integer, Integer> preSum = new HashMap<>();
// base case，即0出现一次
preSum.put(0, 1);

// 遍历数组，求出答案
int sum0 = 0;
int sum1 = 0;
for (int i = 0; i < nums.length; i++) {
 // 求出前i个元素和
 sum0 = sum0 + nums[i];
 // 求出我们要找的前缀和sum0-k
 sum1 = sum0 - k;
 // 如果有该前缀和，更新答案res
 if (preSum.containsKey(sum1)) {
     res = res + preSum.get(sum1);
 }
 // 记录当前i个元素前缀和出现的次数
 preSum.put(sum0, preSum.getOrDefault(sum0, 0) + 1);
}

return res;
}
```
2. 差分数组解决子数组问题
  1. 差分数组技巧一般都和前缀和技巧比较记忆。前缀和技巧，一般用于对不变数组的某个区间元素和的查询；差分数组技巧一般用于对不变数组的某个区间元素进行增减。
  2. 差分数组的一般问题描述：对一个数组的某些区间多次进行增、减操作，最后问数组的值
  3. 差分数组解题思路：
    
    类似前缀和技巧构造的prefix数组，我们先对nums数组构造一个diff差分数组，diff[i]就是nums[i]和nums[i-1]之差：
```
 // 构建差分数组
 int[] diff = new int[nums.length];
 diff[0] = nums[0];
 for (int i = 1; i < nums.length; i++) {
     diff[i] = nums[i] - nums[i - 1];
 }
```
    通过差分数组反推回原来的数组也可以，代码如下：
```
 // 反推回原数组
 int[] nums = new int[diff.length];
 nums[0] = diff[0];
 for (int i = 1; i < diff.length; i++) {
     nums[i] = nums[i - 1] + diff[i];
 }
```
    如果要对nums数组的某个区间[i..j]进行增减操作，对应到diff数组是什么呢？根据反推的步骤，我们可以看出，假如对nums的[i..j]进行+3操作，则相当于diff[i] += 3，并且diff[j+1] -=3。
    
    原理很简单，回想diff数组反推nums数组的过程，diff[i] += 3意味着给nums[i..]所有的元素都加了 3，然后diff[j+1] -= 3又意味着对于nums[j+1..]所有元素再减 3，那综合起来，是不是就是对nums[i..j]中的所有元素都加 3。
    
    我们如果需要对nums某些区间的元素增减，只需要操作diff数组，然后反推回新nums即可。需要注意，如果j+1>=nums.length，说明区间为i到数组最后，所以不用diff[j+1] -=val这个过程。
3. 快速选择算法
  1. 快速选择算法和快速排序算法相似，它一般用于解决无序数组中快速取第k个大小的元素这种问题
  2. 快速选择算法解释：
    
    快速选择算法就是快速排序的简化版，复用了排序的函数，快速定位第 k 大的元素。相当于对数组部分排序而不需要完全排序，从而提高算法效率
    
    复用的排序函数如下：
```
 public int sort(int[] nums, int left, int right) {

     // 将left索引的值作为分界值
     int mid = nums[left];

     // 定义两个指针用来遍历。因为要进行--j，因此j定义为right+1
     int i = left, j = right + 1;

     // 开始排序
     while(true) {
         while(nums[++i] < mid) {
             if (i == right) break;
         }
         while(nums[--j] > mid) {
             if (j == left) break;
         }
         if (i >= j) break;
         // 交换元素
         int temp = nums[i];
         nums[i] = nums[j];
         nums[j] = temp;
     }

     // 将nums[left]即mid交换到应该在的地方
     int temp = nums[j];
     nums[j] = nums[left];
     nums[left] = temp;

     // 最后，返回分界点的索引
     return j;
 }
```

LeetCode算法

LeetCode算法
1. 560.【和为K的子数组】
  
  解题思路：
  
  使用优化后的前缀和解法。
2. 1109.【航班预订统计】
  
  解题思路：
  
  该问题核心就是对数组的某些区间增减，因此使用差分数组技巧解题即可。
3. 215.【数组中的第K个最大元素】
  
  解题思路：
  
  有两种解题思路：二叉堆(优先级队列)解法和快速选择算法解法。
  
  二叉堆解法：
  
  利用小顶堆，让数组中所有元素过一遍小顶堆，在这个过程中，如果堆中元素大于k个，则删除堆顶元素，直到过完数组所有元素，并且堆内元素只有k个，则堆顶的元素就是第k大的元素（因为小顶堆特性，堆顶的是整个堆中最小的元素）。
  
  二叉堆插入和删除的时间复杂度和堆中的元素个数有关，在这里我们堆的大小不会超过k，所以插入和删除元素的复杂度是O(logK)，再套一层 for 循环，总的时间复杂度就是O(NlogK)。空间复杂度很显然就是二叉堆的大小，为O(K)。
  
  二叉堆解法简单不易出错，因此推荐使用该解法
  
  快速选择算法解法：
  
  该解法更加巧妙，时间复杂度更低，是快速排序的简化版
  
  我们知道，快速排序的关键是如下的函数，它可以将分界点索引p前后的元素变成前面全部都是小于p索引的，后边都是大于p索引的：
```
 public int process(int[] nums, int l, int r) {

     // 左右索引相同，分界索引p为l或r
     if (l == right) return l;

     // 将l索引的元素作为分界元素    
     int mid = nums[l];

     // 开始排序。因为先执行--j，因此j应该初始化为r+1
     int i = l, j = r + 1;
     while(true) {
         while(nums[++i] < mid) {
             if (i == r) break;
         }
         while(nums[--j] > mid) {
             if (j == l) break;
         }
         if (i >= j) break;

         // 交换nums[i]和nums[j]
         int temp = nums[i];
         nums[i] = nums[j];
         nums[j] = temp;
     }

     // 将mid值交换到正确的位置，即中间的索引j的位置
     int temp = nums[j];
     nums[j] = nums[l];
     nums[l] = temp;

     // 最后，返回中间索引即j
     return j;
 }
```
  因此，可以看做经过该函数后，中间索引p的元素一定是第p+1大的元素。那么我们可以把p和k进行比较，如果p < k说明第k大的元素在nums[p+1..hi]中，如果p > k说明第k大的元素在nums[lo..p-1]中，我们可以多次调用该函数，这就是快速选择。

2021/06/16 今日算法

知识点

LeetCode算法