缓存旧值
# 1. 两数之和 (opens new window)
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ret = new int[2];
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
int tmp = target-nums[i];
if(map.containsKey(tmp)){
ret[0] = map.get(tmp);
ret[1] = i;
}
map.put(nums[i],i);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 49. 字母异位词分组 (opens new window)
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str:strs){
char[] ch = str.toCharArray();
Arrays.sort(ch);
String k = new String(ch);
map.computeIfAbsent(k,e->new ArrayList<>()).add(str);
}
return new ArrayList<>(map.values());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
# 138. 随机链表的复制 (opens new window)
哈希表中 kv分别存储原节点与复制节点；
class Solution {
public Node copyRandomList(Node head) {
HashMap<Node,Node> map = new HashMap<>();
for(Node p=head;p!=null;p=p.next){
if(!map.containsKey(p)){
map.put(p,new Node(p.val));
}
}
for(Node p=head;p!=null;p=p.next){
if(p.next!=null){
map.get(p).next = map.get(p.next);
}
if(p.random!=null){
map.get(p).random = map.get(p.random);
}
}
return map.get(head);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 217. 存在重复元素 (opens new window)
HashSet的 add方法有重复元素返回 0；
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num:nums){
if(!set.add(num)){
return true;
}
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 290. 单词规律 (opens new window)
map.put 如果第一次插入返回null，已存在key返回oldValue；
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] ss = s.split(" ");
if(ss.length!=pattern.length()){
return false;
}
Map<Object,Integer> map = new HashMap<>();
for(Integer i=0;i<ss.length;i++){
if(map.put(pattern.charAt(i),i) != map.put(ss[i],i)){
return false;
}
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 387. 字符串中的第一个唯一字符 (opens new window)
class Solution {
public int firstUniqChar(String s) {
Map<Character,Boolean> map = new HashMap<>();
char[] cs = s.toCharArray();
for(char c:cs){
map.put(c,!map.containsKey(c));
}
for(int i=0;i<s.length();i++){
if(map.get(cs[i])){
return i;
}
}
return -1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 349. 两个数组的交集 (opens new window)
stream流的用法；
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> s1 = new HashSet<>();
Set<Integer> s2 = new HashSet<>();
for(int a:nums1){
s1.add(a);
}
for(int b:nums2){
if(s1.contains(b)){
s2.add(b);
}
}
return s2.stream().mapToInt(x->x).toArray();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 350. 两个数组的交集 II (opens new window)
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer,Integer> map = new HashMap<>();
for(int a:nums1){
map.put(a,map.getOrDefault(a,0)+1);
}
ArrayList<Integer> list = new ArrayList<>();
for(int b:nums2){
if(map.containsKey(b)){
list.add(b);
map.put(b,map.get(b)-1);
if(map.get(b)==0){
map.remove(b);
}
}
}
return list.stream().mapToInt(x->x).toArray();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 202. 快乐数 (opens new window)
class Solution {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while(n!=1 && !set.contains(n)){
set.add(n);
n = getNext(n);
}
return n==1;
}
int getNext(int n){
int res = 0;
while(n>0){
int tmp = n%10;
res += tmp*tmp;
n /= 10;
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 532. 数组中的 k-diff 数对 (opens new window)
方法一：HashSet
class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> vis = new HashSet<>();
Set<Integer> res = new HashSet<>();
for(int num:nums){
if(vis.contains(num-k)){
res.add(num-k);// [num-k,num]添加数对第一个
}
if(vis.contains(num+k)){
res.add(num);// [num,num+k]
}
vis.add(num);
}
return res.size();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
方法二：排序+二分
class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int res = 0;
// i的limit为n-2，为了lr两个指针做最后一次判断
for(int i=0;i<n-1;){
int target = nums[i]+k;
int l = i+1,r = n-1;
while(l<=r){
int mid = l+(r-l)/2;
if(nums[mid]<target) l=mid+1;
else if(nums[mid]>target) r=mid-1;
else{
res++;
break;
}
}
i++;
while(i<n-1 && nums[i]==nums[i-1]){
i++;
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 594. 最长和谐子序列 (opens new window)
方法一：哈希表
class Solution {
public int findLHS(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
int ans = 0;
for(int num:nums){
if(map.containsKey(num-1)){
ans = Math.max(ans,map.get(num)+map.get(num-1));
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
方法二：排序+双指针
class Solution {
public int findLHS(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int ans = 0;
for(int i=0,j=0;j<n;j++){
while(i<j && nums[j]-nums[i]>1){
i++;
}
if(nums[j]-nums[i]==1){
ans = Math.max(ans,j-i+1);
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 205. 同构字符串 (opens new window)
方法一：直接用API
class Solution {
public boolean isIsomorphic(String s, String t) {
for(int i = 0; i < s.length(); i++){
if(s.indexOf(s.charAt(i)) != t.indexOf(t.charAt(i))){
return false;
}
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
方法二：哈希表
class Solution {
public boolean isIsomorphic(String s, String t) {
int n1 = s.length();
int n2 = t.length();
if(n1!=n2)
return false;
HashMap<Character,Character> map = new HashMap<>();
for(int i=0;i<n1;i++){
char c1 = s.charAt(i);
char c2 = t.charAt(i);
if(map.containsKey(c1)&&map.get(c1)!=c2 ||
!(map.containsKey(c1))&&map.containsValue(c2)){
return false;
}
map.put(c1,c2);
}
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 2501. 数组中最长的方波 (opens new window)
TreeSet
class Solution {
public int longestSquareStreak(int[] nums) {
TreeSet<Long> tset = new TreeSet<>();
for(long num:nums){
tset.add(num);
}
int ans = 0;
Iterator<Long> it = tset.iterator();
while(it.hasNext()){
int cnt = 0;
long x = it.next();
while(tset.contains(x)){
cnt+=1;
x*=x;
}
ans = Math.max(ans,cnt);
}
return ans>1?ans:-1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 554. 砖墙 (opens new window)
class Solution {
public int leastBricks(List<List<Integer>> wall) {
// 记录 除了最右侧的砖块以外的其它砖块的右边缘到砖墙的左边缘距离
Map<Integer,Integer> map = new HashMap<>();
for(List<Integer> widths:wall){
int n = widths.size();
int sum = 0;
for(int i=0;i<n-1;i++){
sum += widths.get(i);
map.put(sum,map.getOrDefault(sum,0)+1);
}
}
int cnt = 0;
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
cnt = Math.max(cnt,entry.getValue());
}
return wall.size()-cnt;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 609. 在系统中查找重复文件 (opens new window)
class Solution {
public List<List<String>> findDuplicate(String[] paths) {
HashMap<String,List<String>> map = new HashMap<>();
for(String path:paths){
String[] values = path.split(" ");
for(int i=1;i<values.length;i++){
String[] doc = values[i].split("\\(");
// 1.txt 2.txt
doc[1] = doc[1].replace(")","");
List<String> list = map.getOrDefault(doc[1],new ArrayList<String>());
list.add(values[0]+"/"+doc[0]);
map.put(doc[1],list);
}
}
List<List<String>> res = new ArrayList<>();
for(String key:map.keySet()){
if(map.get(key).size()>1){
res.add(map.get(key));
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 454. 四数相加 II (opens new window)
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer,Integer> map = new HashMap<>();
int res = 0;
int tmp = 0;
for(int n1:nums1){
for(int n2:nums2){
tmp = n1+n2;
map.put(tmp,map.getOrDefault(tmp,0)+1);
}
}
for(int n3:nums3){
for(int n4:nums4){
tmp = n3+n4;
if(map.containsKey(-tmp)){
res += map.get(-tmp);
}
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 621. 任务调度器 (opens new window)
# 计数
# 395. 至少有 K 个重复字符的最长子串 (opens new window)
class Solution {
public int longestSubstring(String s, int k) {
if(s.length()<k){
return 0;
}
Map<Character,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
map.put(c,map.getOrDefault(c,0)+1);
}
for(char key:map.keySet()){
// 把s按照key分割（子串中无key了）
if(map.get(key)<k){
int res = 0;
for(String t:s.split(String.valueOf(key))){
res = Math.max(res,longestSubstring(t,k));// 子问题
}
return res;
}
}
return s.length();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 187. 重复的DNA序列 (opens new window)
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> ans = new ArrayList<>();
int n = s.length();
Map<String,Integer> map = new HashMap<>();
for(int i=0;i+10<=n;i++){
String subs = s.substring(i,i+10);
int cnt = map.getOrDefault(subs,0);
if(cnt == 1){
ans.add(subs);
}
map.put(subs,cnt+1);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 645. 错误的集合 (opens new window)
方法一：哈希
class Solution {
public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
int n = nums.length;
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
for(int i=1;i<=n;i++){
int cnt = map.getOrDefault(i,0);
if(cnt==2){
res[0] = i;
}else if(cnt==0){
res[1] = i;
}
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
方法二：排序+双指针
class Solution {
public int[] findErrorNums(int[] nums) {
int[] res = new int[2];
int n = nums.length;
Arrays.sort(nums);
int pre = 0;
for(int i=0;i<n;i++){
int cur = nums[i];
if(cur == pre){
res[0] = pre;
}else if(cur-pre>1){
res[1] = pre+1;
}
pre = cur;
}
// 丢失的是 n
if(nums[n-1]!=n){
res[1] = n;
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 697. 数组的度 (opens new window)
class Solution {
public int findShortestSubArray(int[] nums) {
// p1:key出现次数;p2:key第一次出现位置;p3:key最后一次出现位置
Map<Integer,int[]> map = new HashMap<>();
int n = nums.length;
for(int i=0;i<n;i++){
if(map.containsKey(nums[i])){
map.get(nums[i])[0]++;
map.get(nums[i])[2] = i;
}else{
map.put(nums[i],new int[]{1,i,i});
}
}
int maxNum = 0;
int minLen = 0;
// 遍历map,寻找出现最多次数的key，若相同，选择长度较短的
for(Map.Entry<Integer,int[]> entry:map.entrySet()){
int[] val = entry.getValue();
if(val[0]>maxNum){
maxNum = val[0];
minLen = val[2]-val[1]+1;
}else if(val[0]==maxNum){
if(minLen>val[2]-val[1]+1){
minLen = val[2]-val[1]+1;
}
}
}
return minLen;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30