高频数组与字符串算法技巧
在同一个数组/字符串上使用两个索引进行遍历，常见形式：
窗口由左右两个指针[l, r]定义，表示当前考虑的子数组/子串，右指针扩张窗口，左指针收缩窗口。
数组有序，找到两个数的下标，使得和为 target。
public int[] twoSumSorted(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1}; // 题目下标从1开始
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{-1, -1};
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
char c1 = s.charAt(left);
char c2 = s.charAt(right);
if (!Character.isLetterOrDigit(c1)) {
left++;
continue;
}
if (!Character.isLetterOrDigit(c2)) {
right--;
continue;
}
if (Character.toLowerCase(c1) != Character.toLowerCase(c2)) {
return false;
}
left++;
right--;
}
return true;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)public int lengthOfLongestSubstring(String s) {
Map window = new HashMap<>();
int left = 0, right = 0;
int maxLen = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
window.put(c, window.getOrDefault(c, 0) + 1);
// 当窗口中某个字符出现次数 > 1 时，收缩左边界
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
window.put(d, window.get(d) - 1);
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
// 时间复杂度：O(n)
// 空间复杂度：O(k)，k 为字符集大小 public String minWindow(String s, String t) {
if (s.length() < t.length()) return "";
Map need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
Map window = new HashMap<>();
int left = 0, right = 0;
int valid = 0; // 窗口中满足 need 条件的字符种类数
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
while (valid == need.size()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
// 时间复杂度：O(n)
// 空间复杂度：O(k) public int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0;
int minLen = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;
int[] need = new int[26];
int[] window = new int[26];
for (char c : s1.toCharArray()) {
need[c - 'a']++;
}
for (int i = 0; i < s2.length(); i++) {
window[s2.charAt(i) - 'a']++;
if (i >= s1.length()) {
window[s2.charAt(i - s1.length()) - 'a']--;
}
if (Arrays.equals(need, window)) {
return true;
}
}
return false;
}
// 时间复杂度：O(26 * n) ≈ O(n)
// 空间复杂度：O(1)窗口长度为 windowLen，窗口内出现次数最多的字符为 maxCount，若 windowLen - maxCount > K，说明需要收缩窗口。
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int left = 0, right = 0, maxCount = 0, maxLen = 0;
while (right < s.length()) {
int idx = s.charAt(right) - 'A';
count[idx]++;
maxCount = Math.max(maxCount, count[idx]);
right++;
while (right - left - maxCount > k) {
count[s.charAt(left) - 'A']--;
left++;
}
maxLen = Math.max(maxLen, right - left);
}
return maxLen;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)public int removeDuplicates(int[] nums) {
if (nums.length <= 2) return nums.length;
int slow = 2;
for (int fast = 2; fast < nums.length; fast++) {
if (nums[fast] != nums[slow - 2]) {
nums[slow++] = nums[fast];
}
}
return slow;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)允许每个元素出现两次，只需保证 nums[slow-2] != nums[fast] 时才将 fast 元素写入 slow。
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int max = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
int area = h * (right - left);
max = Math.max(max, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)移动短板指针是有依据的：如果移动长板，只会减小宽度且高度不可能变大到超过原来的短板高度，因此面积不会增大。
public List> threeSum(int[] nums) {
List> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
if (nums[i] > 0) break; // 剪枝
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return res;
}
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)（不计结果集） 外层两层循环 O(n²)，内层双指针 O(n)，总时间 O(n³)。
class RateLimiter {
private Deque window = new ArrayDeque<>();
private long interval;
private int maxRequests;
public RateLimiter(long intervalMillis, int maxRequests) {
this.interval = intervalMillis;
this.maxRequests = maxRequests;
}
public synchronized boolean allow() {
long now = System.currentTimeMillis();
while (!window.isEmpty() && now - window.peekFirst() > interval) {
window.pollFirst();
}
if (window.size() < maxRequests) {
window.offerLast(now);
return true;
}
return false;
}
}