学做网站后台开发,长沙网络公司,安徽炒股配资网站开发,移动网站怎么做优化题目
输入一个整数数组和一个整数k#xff0c;请问数组中有多少个数字之和等于k的连续子数组#xff1f;例如#xff0c;输入数组[1#xff0c;1#xff0c;1]#xff0c;k的值为2#xff0c;有2个连续子数组之和等于2。
分析
在从头到尾逐个扫描数组中的数字时求出前…题目
输入一个整数数组和一个整数k请问数组中有多少个数字之和等于k的连续子数组例如输入数组[111]k的值为2有2个连续子数组之和等于2。
分析
在从头到尾逐个扫描数组中的数字时求出前i个数字之和并且将和保存下来。数组的前i个数字之和记为x。如果存在一个jji数组的前j个数字之和为x-k那么数组中从第i1个数字开始到第j个数字结束的子数组之和为k。 这个题目需要计算和为k的子数组的个数。当扫描到数组的第i个数字并求得前i个数字之和是x时需要知道在i之前存在多少个j并且前j个数字之和等于x-k。所以对每个i不但要保存前i个数字之和还要保存每个和出现的次数。分析到这里就会知道我们需要一个哈希表哈希表的键是前i个数字之和值为每个和出现的次数。
解
public class Test {public static void main(String[] args) {int[] nums {1, 1, 1};int result subarraySum(nums, 2);System.out.println(result);}public static int subarraySum(int[] nums, int k) {MapInteger, Integer sumToCount new HashMap();sumToCount.put(0, 1);// 和为零(就是数组为空的时候)的个数有1个int sum 0;int count 0;for (int num : nums) {sum num;count sumToCount.getOrDefault(sum - k, 0);// 获取和为(sum - k)的个数sumToCount.put(sum, sumToCount.getOrDefault(sum, 0) 1);// 设置和为sum的个数}return count;}
}
