int left = 0, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) return 1;
if (sum < target) left++;
else right--;
}
return 0;
Map<Integer, Integer> indexByValue = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (indexByValue.containsKey(need)) {
return new int[] {indexByValue.get(need), i};
}
indexByValue.put(nums[i], i);
}
核心不是背模板,而是把“之前见过的数据”变成可以快速查询的状态。
五、三种高频算法模式
数组、字符串和 Hash 表最常在下面三种模式中组合出现。
1. 频率计数:元素 → 次数
Map<Character, Integer> freq = new HashMap<>();
for (char c : text.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> lastIndex = new HashMap<>();
int left = 0, answer = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastIndex.containsKey(c)) {
left = Math.max(left, lastIndex.get(c) + 1);
}
lastIndex.put(c, right);
answer = Math.max(answer, right - left + 1);
}
class Solution {
public int lengthOfLongestSubstring(String s) {
int[] windows = new int[128];
int left = 0,right = 0;
int result = 0;
while (right < s.length()){
char c = s.charAt(right);
windows[c]++;
right++;
while(windows[c]>1){
windows[s.charAt(left)]--;
left++;
}
result = Math.max(result,right-left);
}
return result;
}
}
评论(0)
暂无评论