滑动窗口
定长滑动窗口
基础
1456. 定长子串中元音的最大数目
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
class Solution {
public int maxVowels(String s, int k) {
char[] myString = s.toCharArray();
int cur = 0, max = 0;
for (int i=0; i<k; i++) {
if (isVowels(myString[i])) {
cur++;
max++;
}
}
// System.out.println(cur);
int tail=0, head=k;
while (head < myString.length) {
if (isVowels(myString[head])) {
cur++;
}
if (isVowels(myString[tail])) {
cur--;
}
// System.out.println(cur);
max = Math.max(max, cur);
head++;
tail++;
}
return max;
}
public boolean isVowels(char c) {
if (c=='a' || c=='e' || c=='i' || c=='o' || c=='u') {
return true;
}
return false;
}
}2269. 找到一个数字的 K 美丽值
一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：
子字符串长度为
k。子字符串能整除
num。
给你整数 num 和 k ，请你返回 num 的 k 美丽值。
注意：
允许有 前缀 0 。
0不能整除任何值。
一个 子字符串 是一个字符串里的连续一段字符序列。
class Solution {
public int divisorSubstrings(int num, int k) {
String string = String.valueOf(num);
int ans = 0;
for (int i=0; i<=string.length()-k; i++) {
String sub = string.substring(i, i+k);
int val = Integer.parseInt(sub);
if (val == 0) continue;
if (num % val == 0) {
ans++;
}
// System.out.println(sub);
}
return ans;
}
}1984. 学生分数的最小差值
给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。
class Solution {
public int minimumDifference(int[] nums, int k) {
if (k==1) return 0;
Arrays.sort(nums);
int min = nums[nums.length-1] - nums[0];
int tail = 0, head=k-1;
while (head < nums.length) {
min = Math.min(nums[head]-nums[tail], min);
head++;
tail++;
}
return min;
}
}643. 子数组最大平均数 I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
class Solution {
public double findMaxAverage(int[] nums, int k) {
double sum = 0, max = 0;
for (int i=0; i<k; i++) {
sum += nums[i];
}
max = sum;
// System.out.println(sum);
int tail=0, head=k;
while (head < nums.length) {
sum = sum + nums[head] - nums[tail];
// System.out.println(sum);
max = Math.max(sum, max);
tail++;
head++;
}
return max/k;
}
}1343. 大小为 K 且平均值大于等于阈值的子数组数目
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
class Solution {
public int numOfSubarrays(int[] arr, int k, int threshold) {
double sum=0;
int length=arr.length;
for (int i=0; i<k; i++) {
sum += arr[i];
}
int head=k, tail=0, target=threshold*k;
int ans= sum >= target ? 1 : 0;
while (head < length) {
sum = sum + arr[head] - arr[tail];
if (sum >= target) {
ans++;
}
head++;
tail++;
}
return ans;
}
}2090. 半径为 k 的子数组平均值
给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。
半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。
构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。
x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。
例如，四个元素
2、3、1和5的平均值是(2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到2。
class Solution {
public int[] getAverages(int[] nums, int k) {
int length=nums.length;
int[] ans = new int[length];
// System.out.println(length);
Arrays.fill(ans, -1);
if (length<2*k + 1) return ans;
int tail=0, head=2*k+1;
double sum=0;
for (int i=0; i<head; i++) {
sum+=nums[i];
}
ans[k] = (int)(sum/(2*k+1));
for (int i=k+1; i<length-k; i++) {
sum = sum + nums[head] - nums[tail];
ans[i] = (int)(sum/(2*k+1));
head++;
tail++;
}
return ans;
}
}2379. 得到 K 个黑块的最少涂色次数
给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。
给你一个整数 k ，表示想要 连续 黑色块的数目。
每一次操作中，你可以选择一个白色块将它 涂成 黑色块。
请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。
class Solution {
public int minimumRecolors(String blocks, int k) {
int length=blocks.length();
char[] string = blocks.toCharArray();
int white=0;
for (int i=0; i<k; i++) {
if (string[i] == 'W') {
white++;
}
}
int min = white;
int head=k, tail=0;
while(head < length) {
if (string[head] == 'W') {
white++;
}
if (string[tail] == 'W') {
white--;
}
min = Math.min(min, white);
tail++;
head++;
}
return min;
}
}1052. 爱生气的书店老板
有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。
在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
请你返回 这一天营业下来，最多有多少客户能够感到满意 。
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
int mins = customers.length;
int total = 0;
for (int i=0; i<mins; i++) {
if (i < minutes) {
total += customers[i];
} else if (grumpy[i] == 0) {
total += customers[i];
}
}
int max = total;
int head=minutes, tail=0;
while (head < mins) {
//如果生气，让他平静
if (grumpy[head] == 1) {
total += customers[head];
}
//如果生气，让他生气着吧
if (grumpy[tail] == 1) {
total -= customers[tail];
}
max = Math.max(total, max);
tail++;
head++;
}
return max;
}
}2841. 几乎唯一子数组的最大和
给你一个整数数组 nums 和两个正整数 m 和 k 。
请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。
如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。
子数组指的是一个数组中一段连续 非空 的元素序列。
class Solution {
public long maxSum(List<Integer> nums, int m, int k) {
long max = 0;
int length = nums.size();
Map<Integer, Integer> count = new HashMap<>();
long total = 0;
for (int i=0; i<k; i++) {
int num = nums.get(i);
total += num;
if (!count.containsKey(num)) {
count.put(num, 1);
} else {
count.put(num, count.get(num)+1);
}
}
if (count.size() >= m) {
max = total;
}
int tail=0, head=k;
while (head < length) {
int num1 = nums.get(head);
int num2 = nums.get(tail);
total = total + num1 - num2;
if (!count.containsKey(num1)) {
count.put(num1, 1);
} else {
count.put(num1, count.get(num1)+1);
}
if (count.get(num2) == 1) {
count.remove(num2);
} else {
count.put(num2, count.get(num2)-1);
}
if (count.size() >= m) {
max = Math.max(total, max);
}
head++;
tail++;
}
return max;
}
}2461. 长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
子数组的长度是
k，且子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列。
class Solution {
public long maximumSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int length = nums.length;
long max=0, cur=0;
for (int i=0; i<k; i++) {
int number = nums[i];
cur += number;
if (!map.containsKey(number)) {
map.put(number, 1);
} else {
map.put(number, map.get(number) + 1);
}
}
if (map.size() == k) {
max = cur;
}
int head=k, tail=0;
while (head < length) {
int number1 = nums[head];
int number2 = nums[tail];
cur = cur + nums[head] - nums[tail];
if (!map.containsKey(number1)) {
map.put(number1, 1);
} else {
map.put(number1, map.get(number1) + 1);
}
if (map.get(number2) == 1) {
map.remove(number2);
} else {
map.put(number2, map.get(number2) - 1);
}
if (map.size() == k) {
max = Math.max(max, cur);
}
tail++;
head++;
}
return max;
}
}1423. 可获得的最大点数
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
class Solution {
public int maxScore(int[] cardPoints, int k) {
int length=cardPoints.length;
if (k == 1) {
return Math.max(cardPoints[0], cardPoints[length-1]);
}
int cur=0;
for (int i=0; i<k; i++) {
cur += cardPoints[i];
}
int max=cur;
if (length == k) {
return max;
}
int head=length-1, tail=k-1;
while (tail >= 0) {
cur = cur + cardPoints[head] - cardPoints[tail];
max = Math.max(cur, max);
tail--;
head--;
}
return max;
}
}2134. 最少交换次数来组合所有的 1 II
交换 定义为选中一个数组中的两个 互不相同 的位置并交换二者的值。
环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。
给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。
class Solution {
public int minSwaps(int[] nums) {
int length = nums.length;
int sum = 0;
if (length <= 3) {
return 0;
}
for (int i=0; i<length; i++) {
sum += nums[i];
}
int count=0;
for (int i=0; i<sum; i++) {
count += nums[i];
}
if (sum == length) {
return 0;
}
int min = sum - count;
int tail=0, head=sum;
while (tail < length) {
count = count + nums[head] - nums[tail];
min = Math.min(min, sum - count);
tail++;
head = (head + 1) % length;
}
return min;
}
}1297. 子串的最大出现次数
给你一个字符串 s ，请你返回满足以下条件且出现次数最大的 任意 子串的出现次数：
子串中不同字母的数目必须小于等于
maxLetters。子串的长度必须大于等于
minSize且小于等于maxSize。
class Solution {
Map<String, Integer> map = new HashMap<>();
Map<Character, Integer> charMap = new HashMap<>();
int maxL;
public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
maxL = maxLetters;
int maxCur=0;
char[] chars = s.toCharArray();
for (int len=minSize; len<=maxSize; len++) {
//初始化
map.clear();
charMap.clear();
int tail=0, head=len;
String sub=s.substring(0, len);
// System.out.println(sub);
for (int i=0; i<len; i++) {
if(!charMap.containsKey(chars[i])) {
charMap.put(chars[i], 1);
} else {
charMap.put(chars[i], charMap.get(chars[i]) + 1);
}
}
map.put(sub, 1);
if (isValid(sub)) {
maxCur = Math.max(maxCur, 1);
}
// System.out.println("here");
while(head < chars.length) {
char a = chars[head];
char b = chars[tail];
if(!charMap.containsKey(a)) {
charMap.put(a, 1);
} else {
charMap.put(a, charMap.get(a) + 1);
}
if(charMap.get(b) != 1) {
charMap.put(b, charMap.get(b) - 1);
} else {
charMap.remove(b);
}
head++;
tail++;
sub = s.substring(tail, head);
// System.out.println(sub);
if (isValid(sub)) {
if (!map.containsKey(sub)) {
map.put(sub, 1);
maxCur = Math.max(maxCur, 1);
} else {
int times = map.get(sub);
// System.out.println(sub + " " + times);
maxCur = Math.max(maxCur, times + 1);
map.put(sub, times+1);
}
}
}
}
return maxCur;
}
public boolean isValid(String substring) {
if (charMap.size() <= maxL) {
return true;
}
return false;
}
}2653. 滑动子数组的美丽值（超时）
给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。
一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。
请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。
子数组指的是数组中一段连续 非空 的元素序列。
class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
int n = nums.length;
// int[] sub = new int[k];
int[] subSorted = new int[k];
int[] res = new int[n-k+1];
for (int i=0; i<k; i++) {
// sub[i] = nums[i];
subSorted[i] = nums[i];
}
Arrays.sort(subSorted);
res[0] = subSorted[x-1] < 0 ? subSorted[x-1] : 0;
int head = k, tail=1;
while (head < n) {
for (int i=tail, j=0; i<=head; i++,j++) {
subSorted[j] = nums[i];
}
Arrays.sort(subSorted);
res[tail] = subSorted[x-1] < 0 ? subSorted[x-1] : 0;
tail++;
head++;
}
return res;
}
}不定长滑动窗口
求最长/最大
3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int head=0, tail=0;
char[] str = s.toCharArray();
int length = str.length;
int max=0;
while (head < length) {
char c = str[head];
if (!map.containsKey(c)) {
map.put(c, head);
max = Math.max(head-tail+1, max);
} else {
while (str[tail] != c) {
map.remove(str[tail]);
tail++;
}
map.put(c, head);
tail++;
}
head++;
}
return max;
}
}1493. 删掉一个元素以后全为 1 的最长子数组
给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。
class Solution {
public int longestSubarray(int[] nums) {
int max=0;
int length=nums.length;
int head=0, tail=0, countZero=0;
while(head <length) {
if (nums[head] == 1) {
max = Math.max(max, head-tail+1);
} else {
if (countZero == 0) {
max = Math.max(max, head-tail+1);
countZero++;
} else {
while (nums[tail] != 0) {
tail++;
}
tail++;
}
}
head++;
}
return max-1;
}
}2730. 找到最长的半重复子字符串
给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。
如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，"0010" 、"002020" 、"0123" 、"2002" 和 "54944" 是半重复字符串，而 "00101022" （相邻的相同数字对是 00 和 22）和 "1101234883" （相邻的相同数字对是 11 和 88）不是半重复字符串。
请你返回 s 中最长 半重复 子字符串 的长度。
class Solution {
public int longestSemiRepetitiveSubstring(String s) {
int max=1, head=1, tail=0;
boolean isRepeat=false;
char[] str = s.toCharArray();
while (head < str.length) {
if (str[head]!=str[head-1]) {
max = Math.max(head-tail+1, max);
} else {
if (!isRepeat) {
max = Math.max(head-tail+1, max);
isRepeat=true;
} else {
while(str[tail]!=str[tail+1]) {
tail++;
}
tail++;
}
}
head++;
}
return max;
}
}904. 水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
class Solution {
public int totalFruit(int[] fruits) {
Map<Integer, Integer> set = new HashMap<>();
int lastFruit = -1, secondLastFruit = -1;
int lastFruitIndex = -1, secondLastFruitIndex = -1;
int head = 0, tail = 0, max = 0;
while (head < fruits.length) {
int type = fruits[head];
if (set.containsKey(type)) {
set.put(type, head);
max = Math.max(head - tail + 1, max);
} else {
if (set.size() < 2) {
set.put(type, head);
max = Math.max(head - tail + 1, max);
} else {
// 移动tail到secondLastFruitIndex + 1
tail = secondLastFruitIndex + 1;
set.remove(secondLastFruit);
set.put(type, head);
}
}
// 更新最后和次最后出现的水果信息
if (lastFruit != type) {
secondLastFruit = lastFruit;
secondLastFruitIndex = lastFruitIndex;
lastFruit = type;
}
lastFruitIndex = head;
head++;
}
return max;
}
}1695. 删除子数组的最大得分
给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。
class Solution {
public int maximumUniqueSubarray(int[] nums) {
int head=0,tail=0,max=0;
int length=nums.length;
Map<Integer, Integer> pos = new HashMap<>();
int cur=0, del=0;
while(head < length) {
if (!pos.containsKey(nums[head])) {
cur += nums[head];
pos.put(nums[head], head);
max = Math.max(max, cur);
} else {
int p = pos.get(nums[head]);
for (;tail <= p; tail++) {
pos.remove(nums[tail]);
cur -= nums[tail];
}
cur += nums[head];
// tail += 1; 循环结束后tail还要+1
pos.put(nums[head], head);
}
// System.out.println(cur);
head++;
}
return max;
}
}2958. 最多 K 个重复元素的最长子数组
给你一个整数数组 nums 和一个整数 k 。
一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。
如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。
请你返回 nums 中 最长好 子数组的长度。
子数组 指的是一个数组中一段连续非空的元素序列。
class Solution {
public int maxSubarrayLength(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int length=nums.length;
int head=0, tail=0;
int maxLen=0;
while(head < length) {
int number = nums[head];
if (!map.containsKey(number)) {
map.put(number, 1);
} else {
int times = map.get(number);
if (times < k) {
map.put(number, times+1);
} else {
//出现次数为2
while (nums[tail] != number) {
map.put(nums[tail], map.get(nums[tail]) - 1);
tail++;
}
//加一减一抵消掉了
tail++;
}
}
maxLen = Math.max(maxLen, head-tail+1);
head++;
}
return maxLen;
}
}2024. 考试的最大困扰度
一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。
给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：
每次操作中，将问题的正确答案改为
'T'或者'F'（也就是将answerKey[i]改为'T'或者'F'）。
请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。
class Solution {
public int maxConsecutiveAnswers(String answerKey, int k) {
int True=0, False=0;
char[] keys = answerKey.toCharArray();
int head=0, tail=0, max=0;
int cur=0;
while (head<keys.length) {
if (keys[head] == 'T') {
True++;
} else {
False++;
}
while (Math.min(True, False) > k) {
if (keys[tail] == 'T') {
True--;
} else {
False--;
}
tail++;
}
head++;
max = Math.max(max, True + False);
}
return max;
}
}1004. 最大连续1的个数 III
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
class Solution {
public int longestOnes(int[] nums, int k) {
int max=0, threshold=0;
int head=0, tail=0;
while (head < nums.length) {
if (nums[head] == 1) {
} else {
if (threshold < k) {
threshold++;
} else {
//找到从后面往前第一个0
while (nums[tail] != 0) {
tail++;
}
tail++;
}
}
max = Math.max(max, head-tail+1);
head++;
}
return max;
}
}1438. 绝对差不超过限制的最长连续子数组
给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
public int longestSubarray(int[] nums, int limit) {
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
int n = nums.length;
int left = 0, right = 0;
int ret = 0;
while (right < n) {
map.put(nums[right], map.getOrDefault(nums[right], 0) + 1);
while (map.lastKey() - map.firstKey() > limit) {
map.put(nums[left], map.get(nums[left]) - 1);
if (map.get(nums[left]) == 0) {
map.remove(nums[left]);
}
left++;
}
ret = Math.max(ret, right - left + 1);
right++;
}
return ret;
}1658. 将 x 减到 0 的最小操作数
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
//思路：转化问题，将找到x和最小操作数转化为找到数组中最长子数组，且和为sum(nums)-x。
class Solution {
public int minOperations(int[] nums, int x) {
int sum=0, n=nums.length;
for (int num : nums) {
sum += num;
}
if (sum == x) {
return n;
}
int target = sum-x;
int head=0, tail=0;
int cur=0, maxLen=0;
while (head < n) {
cur += nums[head];
if (cur > target) {
while (tail < head && cur > target) {
cur -= nums[tail++];
}
}
if (cur == target) {
maxLen = Math.max(maxLen, head-tail+1);
}
head++;
}
return maxLen==0 ? -1 : n-maxLen;
}
}
// [1 ,2 , 6, 8, 11]1838. 最高频元素的频数（gpt修改后的代码）
元素的 频数 是该元素在一个数组中出现的次数。
给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。
执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。
//因为nums是经过排序的，nums[head]必为最大值，sum只要计算与之前的差然后乘以目前的长度加上去就好了
class Solution {
public int maxFrequency(int[] nums, int k) {
Arrays.sort(nums);
int maxLen = 1;
int head = 0, tail = 0;
long sum = 0;
while (head < nums.length) {
if (head > 0) {
// 更新当前的总操作数
sum += (long)(nums[head] - nums[head - 1]) * (head - tail);
}
// 如果当前窗口不满足条件，移动tail来缩小窗口
while (sum > k) {
sum -= nums[head] - nums[tail];
tail++;
}
// 计算当前窗口的最大长度
maxLen = Math.max(maxLen, head - tail + 1);
head++;
}
return maxLen;
}
}2516. 每种字符至少取 K 个
给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。
class Solution {
public int takeCharacters(String s, int k) {
int[] counts = new int[3]; // a,b,c
char[] chars = s.toCharArray();
for (char c : chars) {
counts[c - 'a']++;
}
if (!check(counts, k)) {
return -1;
}
int res = 0;
for (int left = 0 , right = 0; right < s.length(); right++) {
int index = chars[right] - 'a';
counts[index] -- ;
while (counts[index] < k){
counts[chars[left] - 'a']++;
left++;
}
res = Math.max(res , right - left + 1);
}
return s.length() - res;
}
private boolean check(int[] counts, int k) {
if (counts[0] < k || counts[1] < k || counts[2] < k) {
return false;
}
return true;
}
}2831. 找出最长等值子数组
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。
从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。
子数组 是数组中一个连续且可能为空的元素序列。
class Solution {
public int longestEqualSubarray(List<Integer> nums, int k) {
int length=nums.size();
int maxLen=0;
Map<Integer, Integer> map = new HashMap<>();
int head=0, tail=0;
while (head < length) {
int number = nums.get(head);
if (!map.containsKey(number)) {
map.put(number, 1);
maxLen = Math.max(1, maxLen);
} else {
int times = map.get(number);
maxLen = Math.max(times + 1, maxLen);
map.put(number, times + 1);
}
//
int totalTimes=head-tail+1;
while (totalTimes - maxLen > k) {
int number2 = nums.get(tail);
map.put(number2, map.get(number2) - 1);
maxLen = Math.max(maxLen, map.get(number2));
if (map.get(number2) == 0) {
map.remove(number2);
}
tail++;
totalTimes--;
}
head++;
}
return maxLen;
}
} 2.2求最短/最小
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int cur=0;
int head=0, tail=0, min=Integer.MAX_VALUE;
while (head < nums.length) {
cur += nums[head];
// System.out.println(cur);
if (cur >= target) {
while (cur >= target) {
min = Math.min(min, head-tail+1);
cur-=nums[tail];
tail++;
}
}
head++;
}
return min==Integer.MAX_VALUE ? 0 : min;
}
}2904. 最短且字典序最小的美丽子字符串
给你一个二进制字符串 s 和一个正整数 k 。
如果 s 的某个子字符串中 1 的个数恰好等于 k ，则称这个子字符串是一个 美丽子字符串 。
令 len 等于 最短 美丽子字符串的长度。
返回长度等于 len 且字典序 最小 的美丽子字符串。如果 s 中不含美丽子字符串，则返回一个 空 字符串。
对于相同长度的两个字符串 a 和 b ，如果在 a 和 b 出现不同的第一个位置上，a 中该位置上的字符严格大于 b 中的对应字符，则认为字符串 a 字典序 大于 字符串 b 。
例如，
"abcd"的字典序大于"abcc"，因为两个字符串出现不同的第一个位置对应第四个字符，而d大于c。
class Solution {
public String shortestBeautifulSubstring(String s, int k) {
int n=s.length();
char[] string = s.toCharArray();
int head=0, tail=0, minLen=Integer.MAX_VALUE;
int count =0;
while(head < n && string[head] == '0') {
head++;
tail++;
}
String res="";
while(head<n) {
if (string[head] == '1') {
count++;
}
if (count == k) {
if (k == 1) return "1";
int len = head-tail+1;
String sub = s.substring(tail, head + 1);
if (len < minLen) {
res = sub;
minLen = len;
} else if (minLen == len) {
res = (sub.compareTo(res) > 0) ? sub : res;
}
} else if (count > k) {
//找到多余的一的位置
while (tail < head && string[tail] == '0') {
tail++;
}
tail++;
while (tail < head && string[tail] == '0') {
tail++;
}
count--;
int len = head-tail+1;
// System.out.println(head + " " + tail);
String sub = s.substring(tail, head + 1);
if (len < minLen) {
res = sub;
minLen = len;
} else if (minLen == len) {
res = (sub.compareTo(res) < 0) ? sub : res;
}
}
head++;
}
return res;
}
}1234. 替换子串得到平衡字符串
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
//本题只需要窗口外每种字符的数目小于等于平均值即可
class Solution {
public int balancedString(String s) {
int length=s.length();
int[] count = new int[4];
char[] string = s.toCharArray();
for(int i=0; i<length; i++) {
if (string[i] == 'Q') {
string[i] = 'a';
count[0]++;
}
if (string[i] == 'W') {
string[i] = 'b';
count[1]++;
}
if (string[i] == 'E') {
string[i] = 'c';
count[2]++;
}
if (string[i] == 'R') {
string[i] = 'd';
count[3]++;
}
}
if (count[0]==length/4 && count[1]==length/4 && count[2]==length/4) return 0;
int head=0,tail=0;
int min = Integer.MAX_VALUE;
while(head < length) {
char cur = string[head];
count[cur-'a']--;
while (tail < length &&count[0]<=length/4 &&count[1]<=length/4&&count[2]<=length/4&&count[3]<=length/4) {
min = Math.min(min, head-tail+1);
count[string[tail]-'a']++;
tail++;
}
head++;
}
return min;
}
}2875. 无限数组的最短子数组
给你一个下标从 0 开始的数组 nums 和一个整数 target 。
下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。
请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。
class Solution {
public int minSizeSubarray(int[] nums, int target) {
int tail=0, head=0;
int min=Integer.MAX_VALUE;
int cur=0, length=nums.length;
int turn = 0;
while (tail < length) {
cur += nums[head];
// System.out.println(cur);
if (cur >= target) {
while (tail < length && cur > target) {
cur -= nums[tail];
tail++;
}
if (tail == length) break;
if (cur == target) {
min = Math.min(min, head-tail+1 + length * turn);
}
}
head++;
if (head == length) {
head = 0;
turn++;
}
}
return min==Integer.MAX_VALUE ? -1 : min;
}
}1574. 删除最短的子数组使剩余数组有序
给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。
一个子数组指的是原数组中连续的一个子序列。
请你返回满足题目要求的最短子数组的长度。
class Solution {
public int findLengthOfShortestSubarray(int[] arr) {
int l = 0, r = arr.length-1, R = arr.length-1, min = arr.length-1;
//先找到两端的单调子数组
while(l < arr.length-1 && arr[l] <= arr[l+1]) l++;
while(r > 0 && arr[r] >= arr[r-1]) r--;
if(l >= r) return 0;
if(arr[l] <= arr[r]) return r - l - 1;
//然后遍历每个左边单调子数组
for(int i=l; i>=0 && R >= r; i--){
while(R >= r && arr[R] >= arr[i]) R--;
min = Math.min(min,R - i);
}
return Math.min(min,r);
}
}1358. 包含所有三种字符的子字符串数目
给你一个字符串 s ，它只包含三种字符 a, b 和 c 。
请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。
class Solution {
public int numberOfSubstrings(String s) {
int[] count = new int[3];
int length=s.length();
int head=0, tail=0;
int res = 0;
for (int i=0; i<length; i++) {
count[s.charAt(i)-'a']++;
}
if (count[0] == 0 || count[1] == 0 || count[2] == 0) return res;
Arrays.fill(count, 0);
while (head < length) {
count[s.charAt(head)-'a']++;
while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
res += length-head;
count[s.charAt(tail)-'a']--;
tail++;
}
head++;
}
return res;
}
}2962. 统计最大元素出现至少 K 次的子数组
给你一个整数数组 nums 和一个 正整数 k 。
请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。
子数组是数组中的一个连续元素序列。
class Solution {
public long countSubarrays(int[] nums, int k) {
int max=0, times=0;
for (int num : nums) {
if (num > max) {
max = num;
times = 1;
} else if (num == max) {
times++;
}
}
if (times < k) return 0;
long cur=0;
int head=0, tail=0;
int length = nums.length;
long res=0;
while (head < nums.length) {
if (nums[head] == max) {
cur++;
}
while (tail <= head && cur == k) {
//符合要求的，后面延长任何子串都符合
//每次tail++，前面都是新的子串
res += nums.length-head;
if (nums[tail] == max) {
cur--;
}
tail++;
}
head++;
}
return res;
}
}3258. 统计满足 K 约束的子字符串数量 I
给你一个 二进制 字符串 s 和一个整数 k。
如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：
字符串中
0的数量最多为k。字符串中
1的数量最多为k。
返回一个整数，表示 s 的所有满足 k 约束 的
子字符串
的数量。
//前缀和
class Solution {
public int countKConstraintSubstrings(String s, int k) {
int res=0;
char[] chars = s.toCharArray();
int length = chars.length;
int[] preSum = new int[length];
preSum[0] = chars[0] - '0';
for (int i=1; i<length; i++) {
preSum[i] = preSum[i-1] + chars[i]-'0';
}
for (int i=0; i<length; i++) {
for (int j=i; j<length; j++) {
int pre;
if (i==0) {
pre = preSum[j];
} else {
pre = preSum[j]-preSum[i-1];
}
if (pre <= k || pre >= j-i+1-k) {
// System.out.println(i + "," + j);
res+=1;
}
}
}
return res;
}
}//滑动窗口
class Solution {
public int countKConstraintSubstrings(String s, int k) {
char[] chars = s.toCharArray();
int length = chars.length;
int head=0,tail=0;
int res = 0;
int one=0, zero=0;
while (head < length) {
if (chars[head]=='1') {
one++;
} else {
zero++;
}
while (zero > k && one > k) {
if (chars[tail]=='1') {
one--;
} else {
zero--;
}
tail++;
}
res += head-tail+1;
head++;
}
return res;
}
}2799. 统计完全子数组的数目
给你一个由 正 整数组成的数组 nums 。
如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：
子数组中 不同 元素的数目等于整个数组不同元素的数目。
返回数组中 完全子数组 的数目。
子数组 是数组中的一个连续非空序列。
class Solution {
public int countCompleteSubarrays(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (!map.containsKey(num)) {
map.put(num, 1);
}
}
int diffSize = map.size();
map.clear();
int head=0, tail=0, res=0;
while (head < nums.length) {
if (!map.containsKey(nums[head])) {
map.put(nums[head], 1);
} else {
map.put(nums[head], map.get(nums[head]) + 1);
}
while (tail <= head && map.size() == diffSize) {
res += nums.length-head;
if (map.get(nums[tail]) == 1) {
map.remove(nums[tail]);
} else {
map.put(nums[tail], map.get(nums[tail]) - 1);
}
tail++;
}
head++;
}
return res;
}
}2302. 统计得分小于 K 的子数组数目
一个数组的 分数 定义为数组之和 乘以 数组的长度。
比方说，
[1, 2, 3, 4, 5]的分数为(1 + 2 + 3 + 4 + 5) * 5 = 75。
给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。
子数组 是数组中的一个连续元素序列。
class Solution {
public long countSubarrays(int[] nums, long k) {
int length=nums.length;
long sum=0;
long res=0;
int head=0, tail=0;
while (head < length) {
sum += nums[head];
while (tail <= head && sum * (head-tail + 1) >= k) {
sum -= nums[tail];
tail++;
}
if (sum * (head-tail + 1) < k) {
res+= head-tail+1;
}
head++;
}
return res;
}
}2537. 统计好子数组的数目
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。
class Solution {
public long countGood(int[] nums, int k) {
int length=nums.length;
int head=0, tail=0;
long res=0, pairs=0;
Map<Integer, Integer> map = new HashMap<>();
while (head < length) {
if (!map.containsKey(nums[head])) {
map.put(nums[head], 1);
} else {
int count = map.get(nums[head]);
pairs = pairs + getPairs(count + 1) - getPairs(count);
map.put(nums[head], count + 1);
}
while (tail < head && pairs >= k) {
res += length-head;
System.out.println(head);
System.out.println(nums[tail]);
int times = map.get(nums[tail]);
if (times == 1) {
map.remove(nums[tail]);
} else {
pairs = pairs - getPairs(times) + getPairs(times-1);
map.put(nums[tail], times-1);
}
tail++;
}
head++;
}
return res;
}
public long getPairs(int num) {
return num * (num-1) / 2;
}
}2762. 不间断子数组
给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是 不间断 的：
i，i + 1，...，j表示子数组中的下标。对于所有满足i <= i1, i2 <= j的下标对，都有0 <= |nums[i1] - nums[i2]| <= 2。
请你返回 不间断 子数组的总数目。
子数组是一个数组中一段连续 非空 的元素序列。
class Solution {
public long continuousSubarrays(int[] nums) {
int length=nums.length;
int head=0, tail=0;
long res=0;
PriorityQueue<Integer> minQ = new PriorityQueue<>();
// 自定义最大优先队列,只维护队首最大值，队内不保证有序。
PriorityQueue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
while (head < length) {
minQ.add(nums[head]);
maxQ.add(nums[head]);
while (maxQ.peek() - minQ.peek() > 2) {
maxQ.remove(nums[tail]);
minQ.remove(nums[tail]);
tail++;
}
res += head - tail + 1;
head++;
}
return res;
}
}单序列双指针
相向双指针
125. 验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
char[] str = s.toCharArray();
int left=0, right=str.length-1;
while (left < right) {
while (left<str.length && (str[left]<'a' || str[left]>'z') && (str[left]<'0' || str[left]>'9')) {
left++;
}
while (right >= 0 && (str[right]<'a' || str[right]>'z') && (str[right]<'0' || str[right]>'9')) {
right--;
}
if (left > right) {
break;
}
if (str[right] != str[left]) {
return false;
}
right--;
left++;
}
return true;
}
}1750. 删除字符串两端相同字符后的最短长度
给你一个只包含字符 'a'，'b' 和 'c' 的字符串 s ，你可以执行下面这个操作（5 个步骤）任意次：
选择字符串
s一个 非空 的前缀，这个前缀的所有字符都相同。选择字符串
s一个 非空 的后缀，这个后缀的所有字符都相同。前缀和后缀在字符串中任意位置都不能有交集。
前缀和后缀包含的所有字符都要相同。
同时删除前缀和后缀。
请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。
class Solution {
public int minimumLength(String s) {
char[] str = s.toCharArray();
int left=0, right=str.length-1;
while (left < right) {
if (str[left] == str[right]) {
while (left < str.length-1 && str[left] == str[left+1]) {
left++;
}
while (right > 0 && str[right] == str[right-1]) {
right--;
}
left++;
right--;
} else {
break;
}
}
int ans = right-left + 1;
return ans < 0 ? 0 : ans;
}
}2105. 给植物浇水 II
Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。
每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：
Alice 按 从左到右 的顺序给植物浇水，从植物
0开始。Bob 按 从右到左 的顺序给植物浇水，从植物n - 1开始。他们 同时 给植物浇水。无论需要多少水，为每株植物浇水所需的时间都是相同的。
如果 Alice/Bob 水罐中的水足以 完全 灌溉植物，他们 必须 给植物浇水。否则，他们 首先（立即）重新装满罐子，然后给植物浇水。
如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水 更多 的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 次数 。
class Solution {
public int minimumRefill(int[] plants, int capacityA, int capacityB) {
int res=0;
int curA=capacityA, curB=capacityB;
int left=0, right=plants.length-1;
while (left < right) {
if (plants[left] <= curA) {
curA -= plants[left];
} else {
curA = capacityA-plants[left];
res++;
}
if (plants[right] <= curB) {
curB -= plants[right];
} else {
curB = capacityB-plants[right];
res++;
}
left++;
right--;
}
if (left==right) {
if (Math.max(curA, curB) < plants[left]) {
res++;
}
}
return res;
}
}977. 有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
class Solution {
public int[] sortedSquares(int[] nums) {
int n=nums.length;
int left=0, right=n-1;
int pos=n-1;
int[] res = new int[n];
while(left <= right) {
if (Math.abs(nums[left]) < Math.abs(nums[right])) {
res[pos] = (int)Math.pow(nums[right], 2);
right--;
} else {
res[pos] = (int)Math.pow(nums[left], 2);
left++;
}
pos--;
}
return res;
}
}给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x|或者|a - x| == |b - x|且a < b
class Solution {
public List<Integer> findClosestElements(int[] arr, int k, int x) {
int n=arr.length;
int left=0, right=n-1, mid=0;
while (left < right) {
mid = (left + right) / 2;
if (arr[mid] == x) break;
else if (arr[mid] > x) {
right = mid;
} else {
left = mid+1;
}
}
// System.out.println(arr[mid]);
// System.out.println(arr[left]);
List<Integer> list = new ArrayList<>();
int count=0;
if (arr[mid] == x) {
list.add(x);
left=mid-1;
right=mid+1;
count++;
} else if (arr[mid] > x) {
left = mid-1;
right = mid;
} else {
left = mid;
right = mid+1;
}
while (count < k) {
if (left < 0) {
list.add(arr[right++]);
} else if (right >= n) {
list.add(arr[left--]);
} else {
if (Math.abs(x-arr[left]) <= Math.abs(x-arr[right])) {
list.add(arr[left--]);
} else {
list.add(arr[right++]);
}
}
count++;
}
Collections.sort(list);
return list;
}
}ps:也可以使用反向法。
1471. 数组中的 k 个最强值
给你一个整数数组 arr 和一个整数 k 。
设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：
|arr[i] - m| > |arr[j] - m||arr[i] - m| == |arr[j] - m|，且arr[i] > arr[j]
请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。
class Solution {
public int[] getStrongest(int[] arr, int k) {
Arrays.sort(arr);
int[] res = new int[k];
int n = arr.length;
int left=0, right=n-1;
int mid = arr[(n-1)/2];
int pos=0;
while (pos < k) {
if (Math.abs(arr[left]-mid) > Math.abs(arr[right]-mid)) {
res[pos] = arr[left];
left++;
} else {
res[pos] = arr[right];
right--;
}
pos++;
}
return res;
}
}167. 两数之和 II - 输入有序数组
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int[] res=new int[2];
int n=numbers.length;
int left=0, right=n-1;
while(left < right) {
if (numbers[left] + numbers[right] == target) {
res[0] = left+1;
res[1] = right+1;
break;
} else if(numbers[left] + numbers[right] > target) {
right--;
} else {
left++;
}
}
return res;
}
}2824. 统计和小于目标的下标对数目
给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。
class Solution {
public int countPairs(List<Integer> nums, int target) {
int i=0, j=nums.size()-1;
Collections.sort(nums);
int res=0;
while (i<nums.size() && i<j) {
if (nums.get(i) + nums.get(j) < target) {
res += j-i;
i++;
} else {
j--;
}
}
return res;
}
}LCP 28. 采购方案
小力将 N 个零件的报价存于数组 nums。小力预算为 target，假定小力仅购买两个零件，要求购买零件的花费不超过预算，请问他有多少种采购方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1。
class Solution {
public int purchasePlans(int[] nums, int target) {
Arrays.sort(nums);
int i=0, j=nums.length-1;
long res=0;
while (i < nums.length && i < j) {
if (nums[i] + nums[j] <= target) {
res += j-i;
i++;
} else {
j--;
}
}
return (int)(res%1000000007);
}
}15. 三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n=nums.length;
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
int target=0;
for (int i=0; i<n-2; i++) {
if (i>0 && nums[i]==nums[i-1]) {
continue;
}
int left=i+1, right=n-1;
target = -nums[i];
while (left < right) {
if (nums[left] + nums[right] == target) {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[left-1]) right--;
left++;
right--;
} else if (nums[left] + nums[right] > target) {
right--;
} else {
left++;
}
}
}
// Set<List<Integer>> set = new HashSet(ans);
return ans;
}
}16. 最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
class Solution {
public int threeSumClosest(int[] nums, int target) {
int closest= Integer.MAX_VALUE;
int n=nums.length;
int to=0;
Arrays.sort(nums);
for (int i=0; i<n-2; i++) {
int left=i+1, right=n-1;
int cur = 0;
while (left < right) {
cur = nums[i] + nums[left] + nums[right];
closest = Math.abs(target-cur) < Math.abs(closest-target) ? cur : closest;
if (cur < target) {
left++;
} else {
right--;
}
}
}
return closest;
}
}18. 四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n=nums.length;
Arrays.sort(nums);
List<List<Integer>> res=new ArrayList<>();
for (int i=0; i<n-3; i++) {
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
long target1 = target-nums[i];
for (int j=i+1; j<n-2; j++) {
if (j > i+1 && nums[j] == nums[j-1]) {
continue;
}
long target2 = target1-nums[j];
int left=j+1, right=n-1;
while(left<right) {
if (nums[left] + nums[right] == target2) {
res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
// System.out.println(i + " " + j);
} else if (nums[left] + nums[right] < target2) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}611. 有效三角形的个数
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int n=nums.length;
int res=0;
for (int i=n-1; i>1; i--) {
int left=0, right=i-1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]) {
res+= right-left;
right--;
} else {
left++;
}
}
}
return res;
}
}1577. 数的平方等于两数乘积的方法数
给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：
类型 1：三元组
(i, j, k)，如果nums1[i]2 == nums2[j] * nums2[k]其中0 <= i < nums1.length且0 <= j < k < nums2.length类型 2：三元组
(i, j, k)，如果nums2[i]2 == nums1[j] * nums1[k]其中0 <= i < nums2.length且0 <= j < k < nums1.length
class Solution {
public int numTriplets(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
}
private int countTriplets(int[] nums1, int[] nums2) {
int res = 0;
for (int i = 0; i < nums1.length; i++) {
long target = (long) nums1[i] * nums1[i]; // 使用 long 来防止溢出
int left = 0, right = nums2.length - 1;
while (left < right) {
long product = (long) nums2[left] * nums2[right];
if (product == target) {
if (nums2[left] == nums2[right]) {
int count = right - left + 1;
res += count * (count - 1) / 2;
break;
} else {
int leftCount = 1, rightCount = 1;
while (left < right && nums2[left] == nums2[left + 1]) {
leftCount++;
left++;
}
while (left < right && nums2[right] == nums2[right - 1]) {
rightCount++;
right--;
}
res += leftCount * rightCount;
left++;
right--;
}
} else if (product > target) {
right--;
} else {
left++;
}
}
}
return res;
}
}923. 三数之和的多种可能
给定一个整数数组 arr ，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。
由于结果会非常大，请返回 109 + 7 的模。
class Solution {
public int threeSumMulti(int[] arr, int target) {
Arrays.sort(arr);
long res=0;
int length=arr.length;
for (int i=0; i<length-2; i++) {
int left=i+1, right=length-1;
int target1 = target-arr[i];
while (left<right) {
int cur=arr[left]+arr[right];
if (cur > target1) {
right--;
} else if (cur < target1) {
left++;
} else if(arr[left]==arr[right]) {
res += (right-left) * (right-left + 1) / 2;
break;
} else{
int countL = 1;
int countR = 1;
while (left < right && arr[left]==arr[left+1]) {
countL++;
left++;
}
while (left < right && arr[right]==arr[right-1]) {
countR++;
right--;
}
left++;
right--;
res += countL * countR;
}
}
}
return (int) (res % (Math.pow(10, 9) + 7));
}
}923. 三数之和的多种可能
给定一个整数数组 arr ，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。
由于结果会非常大，请返回 109 + 7 的模。
class Solution {
public int threeSumMulti(int[] arr, int target) {
Arrays.sort(arr);
long res=0;
int length=arr.length;
for (int i=0; i<length-2; i++) {
int left=i+1, right=length-1;
int target1 = target-arr[i];
while (left<right) {
int cur=arr[left]+arr[right];
if (cur > target1) {
right--;
} else if (cur < target1) {
left++;
} else if(arr[left]==arr[right]) {
res += (right-left) * (right-left + 1) / 2;
break;
} else{
int countL = 1;
int countR = 1;
while (left < right && arr[left]==arr[left+1]) {
countL++;
left++;
}
while (left < right && arr[right]==arr[right-1]) {
countR++;
right--;
}
left++;
right--;
res += countL * countR;
}
}
}
return (int) (res % (Math.pow(10, 9) + 7));
}
}948. 令牌放置
你的初始 能量 为 power，初始 分数 为 0，只有一包令牌以整数数组 tokens 给出。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。
你的目标是通过有策略地使用这些令牌以 最大化 总 分数。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不是对同一个令牌使用两种方式）：
朝上：如果你当前 至少 有
tokens[i]点 能量 ，可以使用令牌i，失去tokens[i]点 能量 ，并得到1分 。朝下：如果你当前至少有
1分 ，可以使用令牌i，获得tokens[i]点 能量 ，并失去1分 。
在使用 任意 数量的令牌后，返回我们可以得到的最大 分数 。
class Solution {
public int bagOfTokensScore(int[] tokens, int power) {
int max=0, cur=0;
Arrays.sort(tokens);
int n = tokens.length;
int left=0, right=n-1;
while (left <= right) {
if (power >= tokens[left]) {
power -= tokens[left];
cur++;
max = Math.max(max, cur);
// System.out.println("lose power:" + tokens[left]);
left++;
} else if (cur > 0) {
cur--;
power += tokens[right];
// System.out.println("get power:" + tokens[right]);
right--;
} else {
break;
}
}
return max;
}
}11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
class Solution {
public int maxArea(int[] height) {
int n=height.length;
int left=0, right=n-1;
int max = 0;
while (left < right) {
int cur = Math.min(height[left], height[right]) * (right-left);
max = Math.max(max, cur);
if (height[right] < height[left]) {
right--;
} else {
left++;
}
}
return max;
}
}42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
class Solution {
public int trap(int[] height) {
int n=height.length;
int[] leftMax=new int[n];
int[] rightMax=new int[n];
leftMax[0] = height[0];
rightMax[n-1] = height[n-1];
for (int i=1; i<n; i++) {
leftMax[i] = Math.max(height[i],leftMax[i-1]);
}
for (int i=n-2; i>=0; i--) {
rightMax[i] = Math.max(rightMax[i+1], height[i]);
}
int res=0;
for (int i=0; i<n; i++) {
int min = Math.min(leftMax[i], rightMax[i]);
if (min > height[i]) {
res += min - height[i];
}
}
return res;
}
}1616. 分割两个字符串得到回文串
给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： aprefix 和 asuffix ，满足 a = aprefix + asuffix ，同理，由 b 可以得到两个字符串 bprefix 和 bsuffix ，满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。
当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 和 "abc" + "" 都是合法分割。
如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。
注意， x + y 表示连接字符串 x 和 y 。
class Solution {
public boolean checkPalindromeFormation(String a, String b) {
if (isValid(a) || isValid(b)) {
return true;
}
boolean result1=false, result2=false;
int left=0, right=a.length()-1;
while (left < right) {
while (left < right && a.charAt(left) ==b.charAt(right)) {
left++;
right--;
}
if (left >= right) return true;
else {
// System.out.println(a.substring(left, right+1));
// System.out.println(a.substring(left, right));
result1 = isValid(a.substring(left, right+1)) || isValid(b.substring(left, right+1));
break;
}
}
left=0;
right=a.length()-1;
while (left < right) {
while (left < right && b.charAt(left) ==a.charAt(right)) {
left++;
right--;
}
if (left >= right) return true;
else {
result2 = isValid(a.substring(left, right+1)) || isValid(b.substring(left, right+1));
break;
}
}
return result1 || result2;
}
public boolean isValid(String s) {
int left=0, right=s.length()-1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}同向双指针
1346. 检查整数及其两倍数是否存在
给你一个整数数组 arr，请你检查是否存在两个整数 N 和 M，满足 N 是 M 的两倍（即，N = 2 * M）。
更正式地，检查是否存在两个下标 i 和 j 满足：
i != j0 <= i, j < arr.lengtharr[i] == 2 * arr[j]
class Solution {
public boolean checkIfExist(int[] arr) {
Arrays.sort(arr);
int length=arr.length;
int slow=0, fast=0;
while (slow < length && fast < length) {
if (arr[slow] * 2 == arr[fast]) {
if (slow != fast)
return true;
else
fast++;
} else if (arr[slow] * 2 > arr[fast]) {
fast++;
} else {
slow++;
}
}
return false;
}
}532. 数组中的 k-diff 数对
给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：
0 <= i, j < nums.lengthi != j|nums[i] - nums[j]| == k
注意，|val| 表示 val 的绝对值。
class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int length=nums.length;
int big=length-1, small=length-2;
int res=0;
while (small >= 0) {
// System.out.println(small + " " + big);
if (nums[big]-nums[small] == k) {
if (big != small) {
res++;
while (small > 0 && nums[small]==nums[small-1])small--;
while (big > small && nums[big]==nums[big-1])big--;
small--;
big--;
} else {
small--;
}
} else if (nums[big]-nums[small] > k) {
big--;
} else {
small--;
}
}
return res;
}
}
// 0 1 2 3 4 5
// 1 1 3 4 5原地修改
27. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。返回
k。
class Solution {
public int removeElement(int[] nums, int val) {
if (nums.length==0) return 0;
Arrays.sort(nums);
int left=0, right=0;
boolean isLeft=true;
for (int i=0; i<nums.length; i++) {
if (nums[i] == val) {
if (isLeft) {
left=i;
isLeft=false;
}
right=i;
}
}
if(isLeft) return nums.length;
int res = right-left+1;
for(int i=right+1; i<nums.length; i++) {
nums[left] = nums[i];
left++;
}
return nums.length-res;
}
}26. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。返回
k。
class Solution {
public int removeDuplicates(int[] nums) {
int length=nums.length;
int slow=1, fast=1;
while (fast < length) {
if (nums[fast] > nums[fast-1]) {
nums[slow]=nums[fast];
slow++;
}
fast++;
}
return slow;
}
}给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
class Solution {
public int removeDuplicates(int[] nums) {
int length=nums.length;
int slow=1, fast=1;
boolean isTwice=true;
while (fast < length) {
if (nums[fast] > nums[fast-1]) {
nums[slow] = nums[fast];
isTwice = true;
slow++;
} else if (isTwice) {
nums[slow] = nums[fast];
slow++;
isTwice = false;
}
fast++;
}
return slow;
}
}283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
class Solution {
public void moveZeroes(int[] nums) {
int length=nums.length;
int slow=0, fast=0;
while (fast < length) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
while (slow < length) {
nums[slow] = 0;
slow++;
}
}
}905. 按奇偶排序数组
给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。
返回满足此条件的 任一数组 作为答案。
class Solution {
public int[] sortArrayByParity(int[] nums) {
int length=nums.length;
int[] ans = new int[length];
int index=0;
for (int i=0; i<length; i++) {
if (nums[i] % 2 == 0) {
ans[index] = nums[i];
index++;
}
}
for (int i=0; i<length; i++) {
if (nums[i] % 2 == 1) {
ans[index] = nums[i];
index++;
}
}
return ans;
}
}922. 按奇偶排序数组 II
给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。
对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。
你可以返回 任何满足上述条件的数组作为答案 。
class Solution {
public int[] sortArrayByParityII(int[] nums) {
int length=nums.length;
int[] ans = new int[length];
int odd=1, even=0;
for (int i=0; i<length; i++) {
if (nums[i] % 2 == 0) {
ans[even] = nums[i];
even+=2;
} else {
ans[odd] = nums[i];
odd+=2;
}
}
return ans;
}
}2460. 对数组执行操作
给你一个下标从 0 开始的数组 nums ，数组大小为 n ，且由 非负 整数组成。
你需要对数组执行 n - 1 步操作，其中第 i 步操作（从 0 开始计数）要求对 nums 中第 i 个元素执行下述指令：
如果
nums[i] == nums[i + 1]，则nums[i]的值变成原来的2倍，nums[i + 1]的值变成0。否则，跳过这步操作。
在执行完 全部 操作后，将所有 0 移动 到数组的 末尾 。
例如，数组
[1,0,2,0,0,1]将所有0移动到末尾后变为[1,2,1,0,0,0]。
返回结果数组。
注意 操作应当 依次有序 执行，而不是一次性全部执行。
class Solution {
public int[] applyOperations(int[] nums) {
int length=nums.length;
int[] ans = new int[length];
int pre=0, zero=length-1;
for (int i=0; i<length-1; i++) {
if (nums[i]==nums[i+1]) {
if (nums[i] == 0) {
ans[zero--] = nums[i];
} else {
ans[pre++] = nums[i] * 2;
}
nums[i+1] = 0;
} else if (nums[i] == 0){
ans[zero--] = nums[i];
} else {
ans[pre++] = nums[i];
}
}
if (nums[length-1] == 0) {
ans[zero] = 0;
} else {
ans[pre] = nums[length-1];
}
return ans;
}
}1089. 复写零
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
class Solution {
public void duplicateZeros(int[] arr) {
int length=arr.length;
for (int i=0; i<length; i++) {
if (arr[i] == 0) {
for (int j=length-1; j>=i+2; j--) {
arr[j]=arr[j-1];
}
if (i<length-1) arr[i+1] = 0;
i++;
}
}
}
}双序列双指针
双指针
2540. 最小公共值
给你两个整数数组 nums1 和 nums2 ，它们已经按非降序排序，请你返回两个数组的 最小公共整数 。如果两个数组 nums1 和 nums2 没有公共整数，请你返回 -1 。
如果一个整数在两个数组中都 至少出现一次 ，那么这个整数是数组 nums1 和 nums2 公共 的。
class Solution {
public int getCommon(int[] nums1, int[] nums2) {
int p1=0, p2=0;
while (p1 < nums1.length && p2 < nums2.length) {
if (nums1[p1] == nums2[p2]) {
return nums1[p1];
} else if (nums1[p1] < nums2[p2]) {
p1++;
} else {
p2++;
}
}
return -1;
}
}88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// if (m==0) {
// nums1 = nums2;
// return;
// }
if (n==0) return;
int[] tmp = new int[m];
for (int i=0; i< m; i++) {
tmp[i] = nums1[i];
}
int index1=0, index2=0, index=0;
while(index1 < m && index2 < n) {
if (tmp[index1] < nums2[index2]) {
nums1[index] = tmp[index1];
index1++;
} else {
nums1[index] = nums2[index2];
index2++;
}
index++;
}
while (index1 < m) {
nums1[index] = tmp[index1];
index1++;
index++;
}
while (index2 < n) {
nums1[index] = nums2[index2];
index2++;
index++;
}
}
}2570. 合并两个二维数组 - 求和法
给你两个 二维 整数数组 nums1 和 nums2.
nums1[i] = [idi, vali]表示编号为idi的数字对应的值等于vali。nums2[i] = [idi, vali]表示编号为idi的数字对应的值等于vali。
每个数组都包含 互不相同 的 id ，并按 id 以 递增 顺序排列。
请你将两个数组合并为一个按 id 以递增顺序排列的数组，并符合下述条件：
只有在两个数组中至少出现过一次的 id 才能包含在结果数组内。
每个 id 在结果数组中 只能出现一次 ，并且其对应的值等于两个数组中该 id 所对应的值求和。如果某个数组中不存在该 id ，则认为其对应的值等于
0。
返回结果数组。返回的数组需要按 id 以递增顺序排列。
class Solution {
public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
Set<Integer> set=new HashSet<>();
int m=nums1.length;
int n=nums2.length;
for (int i=0; i<m; i++) {
set.add(nums1[i][0]);
}
for (int i=0; i<n; i++) {
set.add(nums2[i][0]);
}
int length=set.size();
int[][] ans = new int[length][2];
int index1=0, index2=0, index=0;
while (index1<m && index2<n) {
if (nums1[index1][0]==nums2[index2][0]) {
ans[index][0]=nums1[index1][0];
ans[index][1]=nums1[index1][1] + nums2[index2][1];
index1++;
index2++;
} else if (nums1[index1][0] > nums2[index2][0]) {
ans[index][0] = nums2[index2][0];
ans[index][1] = nums2[index2][1];
index2++;
} else {
ans[index][0] = nums1[index1][0];
ans[index][1] = nums1[index1][1];
index1++;
}
index++;
}
while (index1<m) {
ans[index][0] = nums1[index1][0];
ans[index][1] = nums1[index1][1];
index1++;
index++;
}
while (index2<n) {
ans[index][0] = nums2[index2][0];
ans[index][1] = nums2[index2][1];
index2++;
index++;
}
return ans;
}
}LCP 18. 早餐组合
小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
class Solution {
public int breakfastNumber(int[] staple, int[] drinks, int x) {
Arrays.sort(staple);
Arrays.sort(drinks);
long ans=0;
int s=0, d=drinks.length-1;
while (d>=0 && s<staple.length) {
if (staple[s] + drinks[d] <= x) {
ans += d+1;
} else {
d--;
continue;
}
s++;
}
return (int)(ans % 1000000007);
}
}1385. 两个数组间的距离值
给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
class Solution {
public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
Arrays.sort(arr2);
Arrays.sort(arr1);
int m=arr1.length, n=arr2.length;
int p=0;
//找到一个大于arr[0]
for(int i=0; i<n; i++) {
if (arr2[i] > arr1[0]) {
p=i;
break;
}
}
int res=0;
for (int i=0; i<m; i++) {
while (p<n && arr2[p] < arr1[i]) {
p++;
}
if ((p>0 && arr1[i]-arr2[p-1] <= d) || (p<n && arr2[p]-arr1[i] <= d)) {
continue;
}
res++;
}
return res;
}
}1855. 下标对中的最大距离
给你两个 非递增 的整数数组 nums1 和 nums2 ，数组下标均 从 0 开始 计数。
下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i 。
返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。
一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。
class Solution {
public int maxDistance(int[] nums1, int[] nums2) {
int m=nums1.length, n=nums2.length;
int index1=m-1, index2=n-1;
int max=0;
while (index1>=0 && index2>=0) {
if (nums2[index2]>=nums1[index1]) {
index1--;
max=Math.max(max, index2-index1-1);
} else {
index2--;
}
}
return max;
}
}925. 长按键入
你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。
你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
class Solution {
public boolean isLongPressedName(String name, String typed) {
int originL = name.length(), typeL=typed.length();
int index1=0, index2=0;
while (index1<originL && index2<typeL) {
if (name.charAt(index1) == typed.charAt(index2)) {
index1++;
index2++;
} else if (index2>0 && typed.charAt(index2-1) == typed.charAt(index2)) {
while (index2<typeL && typed.charAt(index2-1) == typed.charAt(index2)) {
index2++;
}
} else {
return false;
}
}
while (index2<typeL && typed.charAt(index2-1) == typed.charAt(index2)) {
index2++;
}
// System.out.println(index1 + " " + index2);
if (index2 < typeL || index1 < originL) {
return false;
}
return true;
}
}809. 情感丰富的文字
有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。
对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。
例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 s = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = s。
输入一组查询单词，输出其中可扩张的单词数量。
class Solution {
public int expressiveWords(String s, String[] words) {
int n=words.length;
int ans=0;
for (int i=0; i<n; i++) {
String str = words[i];
int index1=0, index2=0;
while (index1 < s.length() && index2<str.length()) {
if (s.charAt(index1) == str.charAt(index2)) {
int times1=1, times2=1;
while(index2<str.length()-1&&str.charAt(index2+1) == str.charAt(index2)) {
index2++;
times2++;
}
while(index1<s.length()-1&&s.charAt(index1+1) == s.charAt(index1)) {
index1++;
times1++;
}
// if (i==2) {
// System.out.println(times1 + " " + times2);
// System.out.println(index1 + " " + index2);
// }
if ((times2>times1) || (times1!=1 && times1<3 && times1!=times2)) {
break;
}
index1++;
index2++;
} else {
break;
}
}
// System.out.println(index1 + " " + index2);
if (index1 == s.length() && index2 == str.length()) {
ans++;
// System.out.println(i);
}
}
return ans;
}
}2337. 移动片段得到字符串
给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
字符
'L'和'R'表示片段，其中片段'L'只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段'R'只有在其右侧直接存在一个 空位 时才能向 右 移动。字符
'_'表示可以被 任意'L'或'R'片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
class Solution {
public boolean canChange(String start, String target) {
char[] chars1 = start.toCharArray();
char[] chars2 = target.toCharArray();
int n=chars1.length;
int i=0,j=0;
while (true) {
while (i<n && chars1[i] == '_') i++;
while (j<n && chars2[j] == '_') j++;
if (i==n && j==n) return true;
if ((i==n&&j!=n) || (j==n&&i!=n) || (chars1[i]!=chars2[j]) || (chars1[i]=='L' && i<j) || (chars1[i]=='R' && i>j))
return false;
i++;
j++;
}
}
}777. 在LR字符串中交换相邻字符
在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个 "LX" 替换一个 "XL"，或者用一个 "XR" 替换一个 "RX"。现给定起始字符串 start 和结束字符串 end，请编写代码，当且仅当存在一系列移动操作使得 start 可以转换成 end 时， 返回 True。
class Solution {
public boolean canTransform(String start, String end) {
char[] chars1 = start.toCharArray();
char[] chars2 = end.toCharArray();
int i=0, j=0;
int n=chars1.length;
while (true) {
while (i<n&&chars1[i]=='X') i++;
while (j<n&&chars2[j]=='X') j++;
if (j==n && i==n) return true;
if ((j==n&&i!=n) || (j!=n&&i==n) || (chars1[i]!=chars2[j]) || (chars1[i]=='L'&&i<j) || (chars1[i]=='R'&&i>j))
return false;
i++;
j++;
}
}
}844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
class Solution {
public boolean backspaceCompare(String s, String t) {
char[] chars1=s.toCharArray();
char[] chars2=t.toCharArray();
int i=chars1.length-1, j=chars2.length-1;
int count1=0, count2=0;
while (true) {
while (i>=0 && (chars1[i]=='#' || count1>0)) {
if (chars1[i] != '#') {
count1--;
} else {
count1++;
}
i--;
}
while (j>=0 && (chars2[j]=='#' || count2>0)) {
if (chars2[j] != '#') {
count2--;
} else {
count2++;
}
j--;
}
if (i==-1 && j==-1) return true;
if ((i!=-1&&j==-1)|| (i==-1 && j!=-1) || chars1[i] != chars2[j] ) {
return false;
}
i--;
j--;
}
}
}986. 区间列表的交集
给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
int length1 = firstList.length;
int length2 = secondList.length;
if (length1 == 0 || length2 == 0) return new int[][]{};
List<int[]> result = new ArrayList<>();
int i = 0, j = 0;
while (i < length1 && j < length2) {
int[] first = firstList[i];
int[] second = secondList[j];
// 判断是否有重叠部分
int start = Math.max(first[0], second[0]);
int end = Math.min(first[1], second[1]);
if (start <= end) { // 只有在有交集时才会加入结果
result.add(new int[]{start, end});
}
// 根据区间的结束位置，决定移动哪个指针
if (first[1] < second[1]) {
i++;
} else {
j++;
}
}
// 将结果从 List 转为二维数组
return result.toArray(new int[result.size()][]);
}
}2070. 每一个查询的最大美丽值
给你一个二维整数数组 items ，其中 items[i] = [pricei, beautyi] 分别表示每一个物品的 价格 和 美丽值 。
同时给你一个下标从 0 开始的整数数组 queries 。对于每个查询 queries[j] ，你想求出价格小于等于 queries[j] 的物品中，最大的美丽值 是多少。如果不存在符合条件的物品，那么查询的结果为 0 。
请你返回一个长度与 queries 相同的数组 answer，其中 answer[j]是第 j 个查询的答案。
class Solution {
public int[] maximumBeauty(int[][] items, int[] queries) {
int length=queries.length;
int[] ans = new int[length];
Arrays.sort(items, (o1, o2) -> o1[1] - o2[1]);
for(int i=0; i<length; i++) {
int max=0;
for (int j=items.length-1; j>=0; j--) {
if (queries[i] >= items[j][0]) {
max = items[j][1];
break;
}
}
ans[i] = max;
}
return ans;
}
}面试题 16.06. 最小差
给定两个整数数组a和b，计算具有最小差绝对值的一对数值（每个数组中取一个值），并返回该对数值的差
class Solution {
public int smallestDifference(int[] a, int[] b) {
Arrays.sort(a);
Arrays.sort(b);
long min=Integer.MAX_VALUE;
int p1=0, p2=0;
while (p1<a.length && p2<b.length) {
if (a[p1] > b[p2]) {
min = Math.min((long)a[p1]-(long)b[p2], min);
p2++;
} else if (a[p1] < b[p2]){
min = Math.min((long)b[p2]-(long)a[p1], min);
p1++;
} else {
return 0;
}
}
return (int)min;
}
}1537. 最大得分
你有两个 有序 且数组内元素互不相同的数组 nums1 和 nums2 。
一条 合法路径 定义如下：
选择数组
nums1或者nums2开始遍历（从下标 0 处开始）。从左到右遍历当前数组。
如果你遇到了
nums1和nums2中都存在的值，那么你可以切换路径到另一个数组对应数字处继续遍历（但在合法路径中重复数字只会被统计一次）。
得分 定义为合法路径中不同数字的和。
请你返回 所有可能 合法路径 中的最大得分。由于答案可能很大，请你将它对 10^9 + 7 取余后返回。
class Solution {
public int maxSum(int[] nums1, int[] nums2) {
int length1 = nums1.length;
int length2 = nums2.length;
int p1=0, p2=0;
long cur1=0, cur2=0;
long res=0;
while (p1<length1 && p2<length2) {
if (nums1[p1] == nums2[p2]) {
res += nums1[p1];
res += Math.max(cur1, cur2);
p1++;
p2++;
cur1=0;
cur2=0;
} else if(nums1[p1] < nums2[p2]) {
cur1 += nums1[p1];
p1++;
} else {
cur2 += nums2[p2];
p2++;
}
}
while (p1 < length1) {
cur1 += nums1[p1];
p1++;
}
while (p2 < length2) {
cur2 += nums2[p2];
p2++;
}
res += Math.max(cur1, cur2);
return (int)(res%1000000007);
}
}判断子序列
392. 判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
class Solution {
public boolean isSubsequence(String s, String t) {
char[] sh = s.toCharArray();
char[] lo = t.toCharArray();
int i=0, j=0;
while (i<sh.length && j<lo.length) {
if (sh[i] == lo[j]) {
i++;
j++;
} else {
j++;
}
}
if (i==sh.length) return true;
return false;
}
}524. 通过删除字母匹配到字典里最长单词
给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
String ans="";
for (String t: dictionary) {
if (isSubsquence(t, s)) {
if (t.length()>ans.length()){
ans = t;
} else if (t.length()==ans.length() && t.compareTo(ans) < 0) {
ans = t;
}
}
}
return ans;
}
public boolean isSubsquence(String s, String t) {
char[] sh = s.toCharArray();
char[] lo = t.toCharArray();
int i=0, j=0;
while (i<sh.length && j<lo.length) {
if (sh[i] == lo[j]) {
i++;
j++;
} else {
j++;
}
}
return i==sh.length;
}
}2486. 追加字符以获得子序列
给你两个仅由小写英文字母组成的字符串 s 和 t 。
现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。
子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。
class Solution {
public int appendCharacters(String s, String t) {
char[] original = s.toCharArray();
char[] str = t.toCharArray();
int length1=original.length, length2=str.length;
int j=0;
for (int i=0; i< length1; i++) {
if (j == length2) {
break;
}
if (original[i] == str[j]) {
j++;
}
}
return length2-j;
}
} 2825. 循环增长使字符串子序列等于另一个字符串
给你一个下标从 0 开始的字符串 str1 和 str2 。
一次操作中，你选择 str1 中的若干下标。对于选中的每一个下标 i ，你将 str1[i] 循环 递增，变成下一个字符。也就是说 'a' 变成 'b' ，'b' 变成 'c' ，以此类推，'z' 变成 'a' 。
如果执行以上操作 至多一次 ，可以让 str2 成为 str1 的子序列，请你返回 true ，否则返回 false 。
注意：一个字符串的子序列指的是从原字符串中删除一些（可以一个字符也不删）字符后，剩下字符按照原本先后顺序组成的新字符串。
class Solution {
public boolean canMakeSubsequence(String str1, String str2) {
char[] str=str1.toCharArray();
char[] substring=str2.toCharArray();
int length1=str.length, length2=substring.length;
int j=0;
for (int i=0; i<length1; i++) {
if (j == length2) break;
if (str[i] == substring[j] || (str[i]-'a') == (substring[j]-'a'+25)%26){
j++;
}
}
return j==length2;
}
}1023. 驼峰式匹配
给你一个字符串数组 queries，和一个表示模式的字符串 pattern，请你返回一个布尔数组 answer 。只有在待查项 queries[i] 与模式串 pattern 匹配时， answer[i] 才为 true，否则为 false。
如果可以将小写字母插入模式串 pattern 得到待查询项 queries[i]，那么待查询项与给定模式串匹配。可以在任何位置插入每个字符，也可以不插入字符。
class Solution {
public List<Boolean> camelMatch(String[] queries, String pattern) {
List<Boolean> ans = new ArrayList<>();
char[] myPattern = pattern.toCharArray();
int length2 = myPattern.length;
for (String query : queries) {
char[] myQuery = query.toCharArray();
int length1 = myQuery.length;
int i=0,j=0;
for (;i<length1; i++) {
if (j < length2 && myPattern[j] == myQuery[i]) {
j++;
} else if (j == length2 || myQuery[i] >= 'A' && myQuery[i] <= 'Z') {
break;
}
}
if (j==length2) {
boolean hasUpper=false;
for (; i<length1; i++) {
if (myQuery[i] >= 'A' && myQuery[i] <= 'Z') {
hasUpper=true;
break;
}
}
ans.add(!hasUpper);
} else {
ans.add(false);
}
}
return ans;
}
}3132. 找出与数组相加的整数 II
给你两个整数数组 nums1 和 nums2。
从 nums1 中移除两个元素，并且所有其他元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。
执行上述操作后，nums1 和 nums2 相等 。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组 相等 。
返回能够实现数组相等的 最小 整数 x 。
class Solution {
public int minimumAddedInteger(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length=nums2.length;
int i=0, j=0, count=0;
int ans = Integer.MAX_VALUE;
int number1=Integer.MAX_VALUE, number2=Integer.MAX_VALUE, number3=Integer.MAX_VALUE;
int diff1=nums2[0]-nums1[0];
for (;i<nums1.length; i++) {
if (j==length) break;
if (nums2[j]-nums1[i] == diff1) {
j++;
} else {
count++;
}
if (count > 2) {
break;
}
}
if (j==length) ans = Math.min(ans, diff1);
i=1;j=0;count=0;
int diff2=nums2[0]-nums1[1];
for (;i<nums1.length; i++) {
if (j==length) break;
if (nums2[j]-nums1[i] == diff2) {
j++;
} else {
count++;
}
if (count > 1) {
break;
}
}
if (j==length) ans = Math.min(ans, diff2);
i=2; j=0; count=0;
int diff3=nums2[0]-nums1[2];
for (;i<nums1.length; i++) {
if (j==length) break;
if (nums2[j]-nums1[i] == diff3) {
j++;
} else {
count++;
}
if (count > 0) {
break;
}
}
if (j==length) ans = Math.min(ans, diff3);
return ans;
}
}522. 最长特殊序列 II
给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。
特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。
s 的 子序列可以通过删去字符串 s 中的某些字符实现。
例如，
"abc"是"aebdc"的子序列，因为您可以删除"aebdc"中的下划线字符来得到"abc"。"aebdc"的子序列还包括"aebdc"、"aeb"和 "" (空字符串)。
class Solution {
public int findLUSlength(String[] strs) {
int length=strs.length;
int ans = 0;
int[] count = new int[length];
for (int i=0; i<length; i++) {
for (int j=0; j<length; j++) {
if (i==j) continue;
if (isSubsequence(strs[i], strs[j])) {
// count[i]=1;
count[j]=1;
}
}
}
for (int i=0; i<length; i++) {
if (count[i] == 0) {
ans = Math.max(ans, strs[i].length());
}
}
return ans == 0 ? -1 : ans;
}
public boolean isSubsequence(String a, String b) {
int length1=a.length(), length2=b.length();
int j=0;
for (int i=0; i<length1 && j<length2; i++) {
if (a.charAt(i) == b.charAt(j)) {
j++;
}
}
return j==length2;
}
}