✨前言
文章目录
一、区域和检索 - 数组不可变
题目描述
给定一个整数数组 nums，处理以下类型的多个查询:
计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/range-sum-query-immutable
思路详解
首先创建一个数组sums，为了方便创建的大小为 传入数组长度+1。
通过循环我们把下标之前的总和存到sums里，那么取范围总值的时候就可以用 后边总值— 前边总值
代码与结果
class NumArray { int[] sums; public NumArray(int[] nums) { int n = nums.length; sums = new int[n + 1]; for (int i = 0; i < n; i++) { sums[i + 1] = sums[i] + nums[i]; } } public int sumRange(int i, int j) { return sums[j + 1] - sums[i]; } }
二、所有奇数长度子数组的和
题目描述
给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sum-of-all-odd-length-subarrays
思路详解
首先想到的就是 三次循环，首先确定字串的起始位置start，寻找所有的奇数长度，通过公式 end = start + length -1 ,确定字串结束位置end，遍历相加即可
代码与结果
class Solution { public int sumOddLengthSubarrays(int[] arr) { int sum = 0; int n = arr.length; for (int start = 0; start < n; start++) { for (int length = 1; start + length <= n; length += 2) { int end = start + length - 1; for (int i = start; i <= end; i++) { sum += arr[i]; } } } return sum; } }
三、和相同的二元子数组
题目描述
给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。
子数组 是数组的一段连续部分。
思路详解
这个思路是通过看官方大大给的解释，假设原数组的前缀和数组为sum，且子数组(i,j] 的区间和为 goal，那么 sum[j]−sum[i]=goal。因此我们可以枚举 j，每次查询满足该等式的 ii 的数量。
具体地，我们用哈希表记录每一种前缀和出现的次数，假设我们当前枚举到元素 nums[j]，我们只需要查询哈希表中元素 sum[j]−goal 的数量即可，这些元素的数量即对应了以当前 j 值为右边界的满足条件的子数组的数量。最后这些元素的总数量即为所有和为 goal 的子数组数量。
在实际代码中，我们实时地更新哈希表，以防止出现i≥j 的情况。
代码与结果
class Solution { public int numSubarraysWithSum(int[] nums, int goal) { int sum = 0; Map<Integer, Integer> cnt = new HashMap<Integer, Integer>(); int ret = 0; for (int num : nums) { cnt.put(sum, cnt.getOrDefault(sum, 0) + 1); sum += num; ret += cnt.getOrDefault(sum - goal, 0); } return ret; } }
✨总结
今天的题还是有些难度的，继续深入研究研究。
😎Procrastination is the thief of time.
拖延乃光阴之窃贼。 -《大卫·科波菲尔》😎
