构建前缀信息
303. 区域和检索 – 数组不可变
- 构建前缀和数组,快速计算子数组区间和
class NumArray {
public int[] prefixSum;
public NumArray(int[] nums) {
prefixSum = new int[nums.length + 1];
// 计算前缀和
for (int i = 1; i
未排序数组中累加和为给定值的最长子数组长度
- 构建前缀和最早出现的位置,返回无序数组中累加和为给定值的最长子数组的长度
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len = in.nextInt();
int k = in.nextInt();
int[] nums = new int[len];
for (int i = 0; i hashMap = new HashMap();
// 初始就有一个前缀和为0
hashMap.put(0, 0);
for (int i = 1; i
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len = in.nextInt();
int k = in.nextInt();
int[] nums = new int[len];
for (int i = 0; i hashMap = new HashMap();
hashMap.put(0, 0);
for (int i = 1; i
60. 和为 K 的子数组
- 构建前缀和出现的次数,返回无序数组中累加和为给定值的子数组的个数
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0;
// 记录前缀和以及出现次数
Map map = new HashMap();
// 前缀和为0的至少出现一次
map.put(0, 1);
int prefixSum = 0;
for (int i = 1; i
未排序数组中累加和为给定值的最长子数组系列问题补1
- 构建前缀和最早出现的位置,返回无序数组中,正负数个数相等的最长子数组的长度
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len = in.nextInt();
int[] nums = new int[len];
for (int i = 0; i map = new HashMap();
map.put(0, 0);
for (int i = 1; i 0)
prefix++;
else if (nums[i - 1]
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len = in.nextInt();
int[] nums = new int[len];
for (int i = 0; i 0 ? 1 : -1) : 0;
}
int res = 0;
// 记录前缀中正数和负数的差值(正数个数-负数个数)
int prefix = 0;
// 记录prefix和其位置
Map map = new HashMap();
map.put(0, 0);
for (int i = 1; i
1124. 表现良好的最长时间段
- 构建前缀和最早出现的位置。表现良好的最长时间段问题
import java.util.HashMap;
import java.util.Map;
class Solution {
public int longestWPI(int[] hours) {
int res = 0;
// 记录前缀中大于8h的天数和小于等于8h的天数之差
int prefix = 0;
// 记录差值和下标
Map map = new HashMap();
map.put(0, 0);
for (int i = 1; i 8 ? 1 : -1;
if (prefix > 0) {
// 从数组开头到当前位置符合要求
res = i;
} else {
// 若当前prefix为-3,则找-4是否已经出现,若出现,则说明-4出现的位置到当前位置的子数组是符合条件的(大于8h的天数严格大于一半)
// 若之前还有-5、-6啥的,其之前一定出现过-4,因为是从0开始加一减一的,先出现-4才可能出现-5、-6
if (map.containsKey(prefix - 1))
res = Math.max(res, i - map.get(prefix - 1));
}
if (!map.containsKey(prefix)) map.put(prefix, i);
}
return res;
}
}
1590. 使数组和能被 P 整除
- 构建前缀和余数最早出现的位置。移除的最短子数组长度,使得剩余元素的累加和能被p整除
import java.util.HashMap;
import java.util.Map;
class Solution {
public int minSubarray(int[] nums, int p) {
// 总体和模p的余数,也是需要删除的部分的累加和模p的余数
int delete = 0;
for (int num : nums) delete = (delete + num) % p;
// 不需要移除子数组
if (delete == 0) return 0;
int res = 0x7fffffff;
// 记录累加和
int prefixSum = 0;
// key为模p的余数,value为该值最后一次出现的位置
Map map = new HashMap();
map.put(0, 0);
for (int i = 1; i
1371. 每个元音包含偶数次的最长子字符串
- 构建前缀奇偶状态最早出现的位置。每个元音包含偶数次的最长子串长度
import java.util.Arrays;
class Solution {
public int findTheLongestSubstring(String s) {
int len = s.length();
// 只有5个元音字符,状态5位,状态总数32种
int[] map = new int[32];
// -2表示这个状态之前没出现过
Arrays.fill(map, -2);
// aeiou 00000
map[0] = -1;
int ans = 0;
// status低5位从低到高分表表示aeiou的奇偶性,0为偶,1为奇
int status = 0;
// aeiou在status中对应的位置
int m;
for (int i = 0; i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net