★ 两数之和
★1. 两数之和
创建一个字典，对于每一个 y，首先查询哈希表中是否存在 target - y，如果存在，则返回结果，否则将 y 插入到哈希表中。或者查询哈希表中是否存在 x，如果存在，则返回结果，否则将 target - x 插入到哈希表中
注意：方法是先把 x 和它的下标放到字典中，然后对后面的 x 在字典中找 target - x。
不能排序，因为找的是索引。a + b = target, 一但 a 确定 b 就确定了，即 a，b 之间存在恒等的关系。
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++){int x = target - nums[i];// 回头找if (map.containsKey(x)) return new int[]{map.get(x), i};map.put(nums[i], i);}return new int[2];}
}
2006. 差的绝对值为 K 的数对数目
|nums[i] - nums[j]| == k
x = y + k or y = x + k
class Solution {public int countKDifference(int[] nums, int k) {int res = 0;// int[] c = new int[200];// for (int x : nums) c[x] ++;// for (int x : nums) ans += c[x + k];Map<Integer, Integer> map = new HashMap<>();for (int x : nums)map.put(x, map.getOrDefault(x, 0) + 1);for (int x : nums)res += map.getOrDefault(x + k, 0);return res;}
}
15. 三数之和
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);int n = nums.length;List<List<Integer>> res = new ArrayList(); for (int i = 0; i < n; i++) {if (nums[i] > 0) return res; // 剪枝if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重！！!// 方法一：二分 133 msfor (int j = i + 1; j < n - 1; j++) {if (nums[i] + nums[j] + nums[j + 1] > 0) break; // 剪枝if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 去重 int x = -nums[i] - nums[j];int left = j + 1, right = n;while (left < right) {int mid = left + right >> 1;if (nums[mid] < x) left = mid + 1;else right = mid;}if (right < n) {List<Integer> tmp = List.of(nums[i], nums[j], nums[right]);if (nums[i] + nums[j] + nums[right] == 0) res.add(tmp);}}// 方法二：双指针 29 msint j = i + 1, k = n - 1;// while (j < k){// int x = nums[i] + nums[j] + nums[k];// if (x > 0) k--;// else if (x < 0) j++;// else {// res.add(List.of(nums[i], nums[j], nums[k]));// while (j < k && nums[j] == nums[j+1]) j++; // 去重// while (j < k && nums[k] == nums[k-1]) k--;// j++; k--;// } // }// 方法三：两数和 329 ms// int pre = Integer.MAX_VALUE, x = nums[i];// Set vis = new HashSet();// for (int j = i + 1; j < n; j++){// int z = nums[j], y = -x - z; // if (z >= 0 && vis.contains(y) && pre != y){// res.add(List.of(x, y, z));// pre = y;// }// vis.add(z);// } }return res;}
}
560. 和为 K 的子数组
借鉴 两数和 的思路 ，利用哈希表，这里是两个前缀和的差。
遍历数组，根据当前项前缀和 acc，在 map 中寻找差为 k 的历史前缀和 pre 即 acc - k。acc - pre = k，求区间的和转换为求前缀和的差。
添加哨兵 map.put(0, 1)，解决前缀和为 k 的情况。
class Solution {public int subarraySum(int[] nums, int k) {int acc = 0, res = 0;Map<Integer, Integer> map = new HashMap<>();for (int x : nums){// 如果已经添加了哨兵 map.put(0, 1); 这一行可以放在后面。计数为 1，左边界为 -1。map.put(acc, map.getOrDefault(acc, 0) + 1); // 统计前一个前缀和，默认 {0 : 1}acc += x; // 当前项的前缀和// 在 map 中找差为 k 的前缀和 pre, acc - pre = k，即 pre = acc - kres += map.getOrDefault(acc - k, 0); }return res;}
}
525. 连续数组
把 0 当作 -1 来统计前缀和，用哈希表记录前缀和第一次出现的下标，两个位置的前缀和相同说明，中间子数组（不包含第一个包含第二个位置）的和为 0， 也就是 0 和 1 个数相等。
class Solution {public int findMaxLength(int[] nums) {int ans = 0, n = nums.length, acc = 0;Map<Integer, Integer> map = new HashMap<>();map.put(0, -1); // 前缀和 0 对应左边界，虚拟成 -1，for (int i = 0; i < n; i++){acc += (nums[i] == 0) ? -1 : 1;if (map.containsKey(acc)) ans = Math.max(ans, i - map.get(acc));else map.put(acc, i);}return ans;}
}
523. 连续的子数组和
两个整数 a、b，若它们除以整数 m 所得的余数相等，则称 a 与 b 对于模 m 同余或 a 同余于 b 模 m。
记作 a≡b (mod m)
读作 a 同余于 b 模 m，或读作 a 与 b 对模 m 同余。
class Solution {public boolean checkSubarraySum(int[] nums, int k) {int acc = 0;Map<Integer, Integer> map = new HashMap<>();map.put(0, -1); // 虚拟左边界for (int i = 0; i < nums.length; i++){acc += nums[i];int rem = acc % k; // 同余if (map.containsKey(rem)){if (i - map.get(rem) >= 2) return true;}else map.put(rem, i); // 保存最小索引 }return false;}
}
1010. 总持续时间可被 60 整除的歌曲
class Solution {public int numPairsDivisibleBy60(int[] time) {int[] rem = new int[60]; // 余数int res = 0;for (int t : time){int x = t % 60;// res += x == 0 ? rem[0] : rem[60 - x];res += rem[(60 - x) % 60];rem[x]++; }return res;}
}
1248. 统计「优美子数组」
奇数为1, 偶数为 0, 子区间和为 k 的区间数。
class Solution {public int numberOfSubarrays(int[] nums, int k) { int[] precnt = new int[nums.length + 1]; int res = 0, acc = 0;for (int x: nums) {precnt[acc]++;acc += x & 1;if (acc >= k) res += precnt[acc - k];}return res;}
}
1371. 每个元音包含偶数次的最长子字符串
子串对应区间，求区间某个字母的出现次数，利用 前缀和 转换成求两个数的差值。
对每个元音字母维护一个前缀和，定义 pre[i][k] 表示在字符串前 i 个字符中，第 k 个元音字母一共出现的次数。假设需要求出 [l, r] 这个区间的子串是否满足条件，那么可以用 pre[r][k]−pre[l−1][k]，在 O(1) 的时间得到第 k 个元音字母出现的次数。对于每一个元音字母，都判断一下其是否出现偶数次。
利用 ★前缀和优化了统计子串的时间复杂度，而枚举所有子串的复杂度仍需要 O(n2)，进一步优化，避免枚举所有子串。考虑枚举字符串的每个位置 i ，计算以它结尾的满足条件的最长字符串长度。其实是要快速找到最小的 j∈[0,i)，满足 pre[i][k]−pre[j][k]（即每一个元音字母出现的次数）均为偶数，那么以 i 结尾的最长字符串 s[j+1, i] 长度就是 i − j。
利用 ★哈希表来优化查找的复杂度，但是只利用前缀和，无法找到 i 和 j 相关的 恒等式，像「1248. 统计优美子数组」是能明确知道两个前缀的差值是恒定的。
对于满足条件的子串而言，两个前缀和 pre[i][k] 和 pre[j][k] 的 奇偶性 一定是相同的。修改前缀和，从维护元音字母出现的次数改作维护元音字母出现次数的奇偶性。只要实时维护每个元音字母出现的奇偶性，那么 s[j+1,i] 满足条件当且仅当对于所有的 k，pre[i][k] 和 pre[j][k] 的奇偶性都相等，再利用 哈希表存储每一种奇偶性（即考虑所有的元音字母）对应 最早出现的位置，边遍历边更新答案。
如果直接以每个元音字母出现次数的奇偶性为哈希表中的键，需要额外定义一个状态：
{a: cnta, // a 出现次数的奇偶性e: cnte, // e 出现次数的奇偶性i: cnti, // i 出现次数的奇偶性o: cnto, // o 出现次数的奇偶性u: cntu // u 出现次数的奇偶性
}
将这么一个结构当作哈希表存储的键值，如果题目稍作修改扩大了字符集，那么维护比较吃力。0 代表出现了偶数次，1 代表出现了奇数次，可以将其 ★状态压缩 到一个二进制数中，第 k 位的 0 或 1 代表了第 k 个元音字母出现的奇偶性。举一个例子，假如到第 i 个位置，u o i e a 出现的奇偶性分别为 1 1 0 0 1，那么就可以将其压成一个二进制数 (11001)2=25(11001)_2=25(11001)2=25 作为它的状态。就可以将 5 个元音字母出现次数的奇偶性压缩到了一个二进制数中，且连续对应了二进制数的 [(00000)2,(11111)2][(00000)_2,(11111)_2][(00000)2,(11111)2] 的范围，转成十进制数即 [0, 31]。不再需要使用哈希表，直接用一个长度为 32 的数组来存储 对应状态出现的最早位置。
边界代码中注释。
class Solution {public int findTheLongestSubstring(String s) {int n = s.length();int[] pos = new int[1 << 5]; // 只有 32 种情况Arrays.fill(pos, -2); // 0 是合法的，-2 表示还没有出现过int res = 0, status = 0;pos[0] = -1; // 左边界设成 -1for (int i = 0; i < n; i++) {status ^= switch(s.charAt(i)) {case 'a' -> 1 << 0;case 'e' -> 1 << 1;case 'i' -> 1 << 2;case 'o' -> 1 << 3;case 'u' -> 1 << 4;default -> 0;};// 左开右闭if (pos[status] != -2) res = Math.max(res, i - pos[status]);else pos[status] = i; // 状态第一次出现的位置，每种状态只记录一次即首次出现。}return res;}
}
