leetcode 724. 尋找數(shù)組的中心索引

題目描述

給定一個(gè)整數(shù)類(lèi)型的數(shù)組 nums，請(qǐng)編寫(xiě)一個(gè)能夠返回?cái)?shù)組 “中心索引” 的方法。

我們是這樣定義數(shù)組 中心索引 的：數(shù)組中心索引的左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和。

如果數(shù)組不存在中心索引，那么我們應(yīng)該返回 -1。如果數(shù)組有多個(gè)中心索引，那么我們應(yīng)該返回最靠近左邊的那一個(gè)。

/*** @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;}leftSum+=nums[i];}return -1
};

560. 和為 K 的子數(shù)組

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，請(qǐng)你統(tǒng)計(jì)并返回 該數(shù)組中和為 k 的子數(shù)組的個(gè)數(shù) 。

子數(shù)組是數(shù)組中元素的連續(xù)非空序列。

思路：
用map存放前綴和出現(xiàn)的位置，用一個(gè)count 維護(hù)出現(xiàn)的次數(shù)。

/*** @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. 和相同的二元子數(shù)組

給你一個(gè)二元數(shù)組 nums ,nums[i] 不是 0 就是 1，和一個(gè)整數(shù) goal ，請(qǐng)你統(tǒng)計(jì)并返回有多少個(gè)和為 goal 的 非空 子數(shù)組。

子數(shù)組 是數(shù)組的一段連續(xù)部分。

示例 1：

輸入：nums = [1,0,1,0,1], goal = 2
輸出：4
解釋：
有 4 個(gè)滿足題目要求的子數(shù)組：[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. 統(tǒng)計(jì)「優(yōu)美子數(shù)組」

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k。如果某個(gè)連續(xù)子數(shù)組中恰好有 k 個(gè)奇數(shù)數(shù)字，我們就認(rèn)為這個(gè)子數(shù)組是「優(yōu)美子數(shù)組」。

請(qǐng)返回這個(gè)數(shù)組中 「優(yōu)美子數(shù)組」 的數(shù)目。

思路：簡(jiǎn)化數(shù)組 + 930. 和相同的二元子數(shù)組

var numberOfSubarrays = function(nums, k) {// 簡(jiǎn)化數(shù)組nums = nums.map(item=>item%2===0?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 整除的子數(shù)組

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，返回其中元素之和可被 k 整除的（連續(xù)、非空） 子數(shù)組 的數(shù)目。

思路：

x - y 能夠被 k 整除，

? （x - y）% k = 0

? x % k - y % k = 0

? x % k = y % k

用map存儲(chǔ)presum % k 的結(jié)果，如果有相同的 ，則說(shuō)明 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; //如果是負(fù)數(shù)，需要 + 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. 連續(xù)的子數(shù)組和

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，編寫(xiě)一個(gè)函數(shù)來(lái)判斷該數(shù)組是否含有同時(shí)滿足下述條件的連續(xù)子數(shù)組：

• 子數(shù)組大小 至少為 2 ，且
• 子數(shù)組元素總和為 k 的倍數(shù)。

如果存在，返回 true ；否則，返回 false 。

如果存在一個(gè)整數(shù) n ，令整數(shù) x 符合 x = n * k ，則稱(chēng) x 是 k 的一個(gè)倍數(shù)。0 始終視為 k 的一個(gè)倍數(shù)。

思路：

map ：key 存放preSum，value存放第一次出現(xiàn)的索引。只要最長(zhǎng)的大于等于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 % k+k)%k;if(map.has(key)){if(i - map.get(key) >= 2){return true;}}else{map.set(key, i);}}return false;
};