東莞做網(wǎng)站一年費(fèi)用百度指數(shù)明星搜索排名
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;
};