上海免费做网站公司,丈哥seo博客工具,wordpress调用文章第一张图片,旅游网站建设需求分析leetcode 724. 寻找数组的中心索引
题目描述
给定一个整数类型的数组 nums#xff0c;请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组 中心索引 的#xff1a;数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组 中心索引 的数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引那么我们应该返回 -1。如果数组有多个中心索引那么我们应该返回最靠近左边的那一个。
/*** param {number[]} nums* return {number}*/
var pivotIndex function(nums) {let sum nums.reduce((a, b) a b, 0);let leftSum 0;for(let i 0; i nums.length; i){if(leftSum sum - leftSum-nums[i]){return i;}leftSumnums[i];}return -1
};560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k 请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
思路 用map存放前缀和出现的位置用一个count 维护出现的次数。
/*** param {number[]} nums* param {number} k* return {number}*/
var subarraySum function(nums, k) {let res 0;let map new Map();map.set(0, 1);let prefixSum 0;for(let i 0; i nums.length; i){prefixSum nums[i];if(map.has(prefixSum - k)){res map.get(prefixSum - k);}if(map.has(prefixSum)){map.set(prefixSum, map.get(prefixSum) 1);}else{map.set(prefixSum, 1);}}return res;
};930. 和相同的二元子数组
给你一个二元数组 nums ,nums[i] 不是 0 就是 1和一个整数 goal 请你统计并返回有多少个和为 goal 的 非空 子数组。
子数组 是数组的一段连续部分。
示例 1
输入nums [1,0,1,0,1], goal 2
输出4
解释
有 4 个满足题目要求的子数组[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]
示例 2
输入nums [0,0,0,0,0], goal 0
输出15/*** param {number[]} nums* param {number} goal* return {number}*/
var numSubarraysWithSum function(nums, goal) {let map new Map();map.set(0, 1);let res 0;let prefixSum 0;for(let i 0; i nums.length; i){prefixSum nums[i];if(map.has(prefixSum - goal)){res map.get(prefixSum - goal);}if(map.has(prefixSum)){map.set(prefixSum, map.get(prefixSum) 1);}else{map.set(prefixSum, 1);}}return res;
};leetcode1248. 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
思路简化数组 930. 和相同的二元子数组
var numberOfSubarrays function(nums, k) {// 简化数组nums nums.map(itemitem%20?0:1)let res 0;let map new Map();map.set(0, 1);let prefixSum 0;for(let i 0; i nums.length; i){prefixSum nums[i];if(map.has(prefixSum - k)){res map.get(prefixSum - k);}if(map.has(prefixSum)){map.set(prefixSum, map.get(prefixSum) 1);}else{map.set(prefixSum, 1);}}return res;
};974. 和可被 K 整除的子数组
给定一个整数数组 nums 和一个整数 k 返回其中元素之和可被 k 整除的连续、非空 子数组 的数目。
思路
x - y 能够被 k 整除
⇒ x - y% k 0
⇒ x % k - y % k 0
⇒ x % k y % k
用map存储presum % k 的结果如果有相同的 则说明 x - y 能够被 k 整除
/*** param {number[]} nums* param {number} k* return {number}*/
var subarraysDivByK function(nums, k) {let res 0;let map new Map();map.set(0, 1);let prefixSum 0 ;for(let i 0; i nums.length; i){prefixSum nums[i];let key (prefixSum % k k) % k; //如果是负数需要 k 修正如果k 后大于k需要%k。if(map.has(key)){res map.get(key);map.set(key, map.get(key) 1);}else{map.set(key, 1);}}return res;
};523. 连续的子数组和
给你一个整数数组 nums 和一个整数 k 编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组
子数组大小 至少为 2 且子数组元素总和为 k 的倍数。
如果存在返回 true 否则返回 false 。
如果存在一个整数 n 令整数 x 符合 x n * k 则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。
思路
map key 存放preSumvalue存放第一次出现的索引。只要最长的大于等于2 即为存在。
/*** param {number[]} nums* param {number} k* return {boolean}*/
var checkSubarraySum function(nums, k) {let map new Map();map.set(0, -1);let prefixSum 0;for(let i 0; i nums.length; i){prefixSum nums[i];let key (prefixSum % kk)%k;if(map.has(key)){if(i - map.get(key) 2){return true;}}else{map.set(key, i);}}return false;
};
