560. 和为K的子数组
| 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 |
|---|
注：因为此题数组并非是递增的，而且可能存在负数，所以使用滑动窗口解法是不合适的。
题解思路1：暴力解法
尝试将每一个数字都作为一次起始节点，暴力遍历后面的所有数字。
public class Solution {public int subarraySum(int[] nums, int k) {int count = 0;int len = nums.length;for (int left = 0; left < len; left++) {int sum = 0;// 区间里可能会有一些互相抵销的元素for (int right = left; right < len; right++) {sum += nums[right];if (sum == k) {count++;}}}return count;}}
题解思路2：前缀和
1、求解出前缀和数组。
2、双重遍历是否有匹配的两个前缀和满足相减为需要的目标值。
public class Solution {
public int subarraySum(int[] nums, int k) {
int len = nums.length;
// 计算前缀和数组
int[] preSum = new int[len + 1];
preSum[0] = 0;
for (int i = 0; i < len; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
int count = 0;
for (int left = 0; left < len; left++) {
for (int right = left; right < len; right++) {
// 区间和 [left..right]，注意下标偏移
if (preSum[right + 1] - preSum[left] == k) {
count++;
}
}
}
return count;
}
}
题解思路3：前缀和+哈希表
1、求解前缀和
2、通过哈希表存储前缀和，方便获取。键为前缀和的值，值为当前前缀和的个数
public class Solution {
public int subarraySum(int[] nums, int k) {
// key：前缀和，value：key 对应的前缀和的个数
Map<Integer, Integer> preSumFreq = new HashMap<>();
// 对于下标为 0 的元素，前缀和为 0，个数为 1
preSumFreq.put(0, 1);
int preSum = 0;
int count = 0;
for (int num : nums) {
preSum += num;
// 先获得前缀和为 preSum - k 的个数，加到计数变量里
if (preSumFreq.containsKey(preSum - k)) {
count += preSumFreq.get(preSum - k);
}
// 然后维护 preSumFreq 的定义
preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
}
return count;
}
}
注：在计算前缀和的同时，获取是否存在匹配的情况。如果通过存储完再遍历获取一边，就会出现解被重复选取的情况。
42. 接雨水
| 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1：  输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 |
|---|
题解思路1：按行求解
分层求解，求第 i 层的水，遍历每个位置，如果当前的高度小于 i ，并且两边有高度大于等于 i 的，说明这个地方一定有水，水就可以加一。
首先使用一个变量temp保存当前累计的水，初始化为0，从左到右遍历墙的高度，遇到高度大于等于 i 的时候，开始更新temp。更新原则：遇到高度小于 i 的就把temp 加1，遇到高度大于等于 i 的，就把temp加在最后的res中，temp置零，重复之前的步骤即可。
注：如果当前位置的高度小于层数的话且满足左右存在墙的话，那么必定会有水出现。
class Solution {
public int trap(int[] height) {
int sum=0;
int max=getMax(height);//找到最大的高度，以便遍历
for(int i=1;i<=max;i++){
boolean isStart=false;//标记是否开始更新 temp
int temp=0;
for(int j=0;j<height.length;j++){
if(isStart&&height[j]<i)
temp++;
if(height[j]>=i){
sum+=temp;
temp=0;
isStart=true;//主要用于第一次标记开始执行。
}
}
}
return sum;
}
private int getMax(int[] height){
int max=0;
for(int num:height){
max=Math.max(max,num);
}
return max;
}
}
题解思路2：按列求解
分为三种情况进行求解：
1、当前列小于左右边最高的墙
2、较矮的墙小于当前列的墙的高度
3、较矮的墙的高度等于当前列的墙的高度
class Solution {
public int trap(int[] height) {
int sum=0;
//最两端的列不需要考虑，因为一定不会有水，所以坐标从下标1到length-2；
for(int i=1;i<height.length-1;i++){
int max_left=0;
//找到左边最高的
for(int j=i-1;j>=0;j--){
if(height[j]>max_left)
max_left=height[j];
}
int max_right=0;
//找到右边的最高的
for(int j=i+1;j<height.length;j++){
if(height[j]>max_right)
max_right=height[j];
}
//找出两端较小的
int min=Math.min(max_right,max_left);
//当前列的高度
if(min>height[i]){
sum+=(min-height[i]);
}
}
return sum;
}
}
题解思路3：动态规划
在题解思路2中，我们可以发现每一个求解左右最大值的时候都进行了重复的计算，其实我们可以通过dp数组的形式来记录。
max_left[ i ]代表第 i 列左边最高的墙的高度，max_right[ i ]代表第 i 列右边的最高的墙的高度
max_left [ i ] = Max(max_left [ i-1 ]，height[ i-1 ])。它前边的墙的左边的最高高度和它前边的墙的高度选一个较大的，就是当前列左边最高的墙了。
max_right[ i ] = Max(max_right[ i+1 ],height[ i+1 ]) 。它后边的墙的右边的最高高度和它后边的墙的高度选一个较大的，就是当前列右边最高的墙了。
class Solution {
public int trap(int[] height) {
int sum=0;
int[] max_left=new int[height.length];
int[] max_right=new int[height.length];
for(int i=1;i<height.length-1;i++){
max_left[i]=Math.max(max_left[i-1],height[i-1]);
}
for(int i=height.length-2;i>=0;i--){
max_right[i]=Math.max(max_right[i+1],height[i+1]);
}
for(int i=1;i<height.length-1;i++){
int min=Math.min(max_left[i],max_right[i]);
if(min>height[i])
sum+=(min-height[i]);
}
return sum;
}
}
题解思路4：双指针（牛逼）
动态规划中，我们常可以对空间复杂度进行进一步的优化
例如这道题中，max_left[ i ]和max_right[ i ]数组中的元素我们其实只用了一次，然后就再也不会使用。所以我们可以不采用数组，只使用一个元素就行了。
因为数组从左到右遍历，所以可以很轻松的就把左数组去掉。但是右数组应该怎么操作?
height[left-1]是可能成为max_left的变量，同理，height[ right+1 ]是可能成为right_max的变量。
这里我存在理解上的一个误区，就是我本能的认为，代码是通过 for循环中的 i 来控制索引遍历的。但是其实 i 只是用于控制总数量，实际遍历是通过左右指针两个索引来实现。
判断左右边界哪个是完全可靠的。
class Solution {
public int trap(int[] height) {
int sum=0;
int max_left=0;//左边的最大值；
int max_right=0;//右边的最大值；
int left=1;//当前左下标
int right=height.length-2;//当前右下标
//从左往右遍历
for(int i=1;i<height.length;i++){
//从左往右更新
if(height[left-1]<height[right+1]){
max_left=Math.max(max_left,height[left-1]);
int min=max_left;
if(min>height[left]){
sum+=(min-height[i]);
}
left++;
}else{
max_right=Math.max(max_right,height[right+1]);
int min=max_right;
if(min>height[right]){
sum+=(min-height[right]);
}
right--;
}
}
return sum;
}
}
题解思路5：栈
当遍历墙的高度时，如果当前高度小于栈顶的墙高度，说明这里会有积水。我们将墙的高度的下标入栈。
如果当前高度大于栈顶的墙的高度，说明之前的积水到这里就会停下， 我们可以计算下有多少积水。计算完，就把当前的墙继续入栈。作为新的积水的墙。
总体的原则就是，
1、当前高度小于等于栈顶高度，入栈，指针后移。
2、当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。
注：这里有一个点是需要注意的：就是如果当前元素的大小大于栈顶元素的时候，栈顶元素是要弹出的，然后判断栈是不是空，如果是空的话也就意味着不会增加水的体积。
class Solution {
public int trap(int[] height) {
int sum=0;
Stack<Integer> stack=new Stack<>();
int current=0;
while(current<height.length){
while(!stack.isEmpty()&&height[current]>height[stack.peek()]){
int h=height[stack.pop()];//取出栈顶元素
if(stack.isEmpty())
break;
int distance=current-stack.peek()-1;
int min=Math.min(height[current],height[stack.peek()]);
sum+=(min-h)*distance;
}
stack.push(current);
current++;
}
return sum;
}
}
若有收获，就点个赞吧
0 人点赞
