Java实现 LeetCode 560 和为K的子数组(某著名排序大法改编)
2024-09-07 12:22:32
560. 和为K的子数组
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。
PS:
先附上简单一些的
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int sum = 0, ret = 0;
for(int i = 0; i < nums.length; ++i) {
sum += nums[i];
if(map.containsKey(sum-k))
ret += map.get(sum-k);
map.put(sum, map.getOrDefault(sum, 0)+1);
}
return ret;
}
}
PS:
改编自某排序大法
class Solution {
public int subarraySum(int[] nums, int k) {
int sum = 0;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int n : nums) {
sum += n;
min = Math.min(min, sum);
max = Math.max(max, sum);
}
int[] sums = new int[max - min + 1];
int count = 0;
sum = 0;
for (int n : nums) {
sum += n;
int target = sum - min - k;
if (target >= 0 && target < sums.length) {
count += sums[target];
}
sums[sum - min]++;
}
if (k - min >= 0 && k - min < sums.length) {
count += sums[k - min];
}
return count;
}
}
最新文章
- Mysql存储过程(四)——异常处理
- php 页面传递数组元素
- Spring中加载多个Properties配置文件
- .NET三层架构例子超链接可以点击显示内容页面
- 110. Balanced Binary Tree
- Nginx实现静态资源的缓存
- swift:用UITabBarController、UINavigationController、模态窗口简单的搭建一个QQ界面
- 用原生js模仿jquery
- JavaScript IDE
- .Net程序员学用Oracle系列(5):三大数据类型
- LanSoEditor_advance1.8.0 视频编辑的高级版本
- FMS配置小结
- Objective-C 自定义UISlider滑杆 分段样式
- Spark核心类:弹性分布式数据集RDD及其转换和操作pyspark.RDD
- 学习笔记: Expression表达式目录树详解和扩展封装
- jmeter下载和配置
- python之第三方模块安装
- 解决angular页面值闪现问题
- unity, ComputeScreenPos 作用
- 自定义WPF窗体形状