.net最新网站开发,重庆微信网站建设报价,高端网站开发 金蝶,滴滴优惠券网站怎么做的303. 区域和检索 - 数组不可变
给定一个整数数组 nums#xff0c;求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和#xff0c;包含 i, j 两点。
示例#xff1a;
给定 nums [-2, 0, 3, -5, 2, -1]#xff0c;求和函数为 sumRange()
sumRange(0, 2) - 1 sumRange…303. 区域和检索 - 数组不可变
给定一个整数数组 nums求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和包含 i, j 两点。
示例
给定 nums [-2, 0, 3, -5, 2, -1]求和函数为 sumRange()
sumRange(0, 2) - 1 sumRange(2, 5) - -1 sumRange(0, 5) - -3 说明:
你可以假设数组不可变。 会多次调用 sumRange 方法。
Code 303
type NumArray struct {Value []int
}func Constructor(nums []int) NumArray {arr : NumArray{[]int{0}} // 浪费第一个空间// 1, 2, 3, 4, 5for i, v : range nums {// 1, 3, 6, 10, 15arr.Value append(arr.Value, v arr.Value[i])}return arr
}func (this *NumArray) SumRange(i int, j int) int {// i 0; j 3 // [31] - [0] 15 - 1 14 1 2 3 4 return this.Value[j1] - this.Value[i]
}560. 和为K的子数组
给定一个整数数组和一个整数 k你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums [1,1,1], k 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。 说明 :
数组的长度为 [1, 20,000]。 数组中元素的范围是 [-1000, 1000] 且整数 k 的范围是 [-1e7, 1e7]。
Code 560
func subarraySum(nums []int, k int) int { res , m , sum : 0, make(map[int]int,0),0m[0] 1for i:0;ilen(nums);i{sum nums[i]if _,ok : m[sum-k];ok{res m[sum-k]}m[sum]}return res
}1248. 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1
输入nums [1,1,2,1,1], k 3 输出2 解释包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。 示例 2
输入nums [2,4,6], k 1 输出0 解释数列中不包含任何奇数所以不存在优美子数组。 示例 3
输入nums [2,2,2,1,2,2,1,2,2,2], k 2 输出16
提示
1 nums.length 50000 1 nums[i] 10^5 1 k nums.length
Code 1248 这个题严格来说是动态规划的范畴 func numberOfSubarrays(nums []int, k int) int {dp : make([]int, 0)cnt, ret : 0, 0for i : 0; i len(nums); i {cnt// 每次遇到奇数。记录他前面的偶数个数if nums[i]%2 1 {dp append(dp, cnt)cnt 0}if len(dp) k {ret dp[len(dp) - k]}}return ret
}
