# 算法：HashTable、List、Map、Set-实战

## leetcode:242有效字母异位词

### 第一种解法：排序

```class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
byte[] ss = t.getBytes();
byte[] tt = s.getBytes();
Arrays.sort(ss);                                  //排序
Arrays.sort(tt);
for (int i = 0 ; i < ss.length ; i++){
if (ss[i] != tt[i]) {                        //比较是否相等
return false;
}
}
return true;
}
}```

```class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
final Map<Character, Integer> map = new HashMap<>();
for (int i = 0 ; i < s.length() ;i++) {                //根据元素计数
Character c = s.charAt(i);
Integer num = map.get(c);
if (num != null) {
map.put(c, num + 1);
} else {
map.put(c, 1);
}
}
for (int i = 0 ; i < s.length() ;i++) {                //根据元素 反计数
Character c = t.charAt(i);
Integer num = map.get(c);
if (num != null) {
map.put(c, num-1);
} else {
return false;
}
}
for (Map.Entry<Character,Integer> entry:map.entrySet()){
if (entry.getValue() != 0) {
return false;
}
}
return true;
}
}```

```    public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] counter = new int[26];
for (int i = 0; i < s.length(); i++) {
counter[s.charAt(i) - 'a']++;                            //这相当于哈希表
if (--counter[t.charAt(i) - 'a'] < 0) return false;
}
for (int count : counter) {
if (count != 0) return false;
}
return true;
}```

## leetcode:1两数之和

### 方法一、暴力法

```class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i+ 1; j <nums.length; j++) {
if (i == j) continue;
if (nums[i] + nums[j] == target) return new int[]{i,j};
}
}
return null;
}
}```

### 方法二、利用Map存取下标和值

``` public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0 ; i < nums.length ; i++) {
int result = target - nums[i];
if (map.containsKey(result)) return new int[]{i,map.get(result)};
map.put(nums[i],i);
}
return null;
}```

leetcode:15三数之和

### 方法一、暴力法

```    public List<List<Integer>> threeSum2(int[] nums) {
List list = new ArrayList<List<Integer>>();
Set set = new HashSet();
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
for (int t = j + 1; t < nums.length; t++) {
if (nums[i] + nums[j] + nums[t] == 0){
int[] arr = {nums[i] , nums[j] , nums[t]};
Arrays.sort(arr);
if (set.contains(arr[0]+""+ arr[1]+""+ arr[2])) break;
List stor = new ArrayList<Integer>();
break;
}
}
}
}
return list;
}
//或者不用SET 去重
public List<List<Integer>> threeSum2(int[] nums) {
final ArrayList<List<Integer>> lists = new ArrayList<>();
Arrays.sort(nums);

// long count = 0;

for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int maxIndex = nums.length - 1;
for (int j = i + 1; j < maxIndex; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}

for (int k = maxIndex; k > j; k--) {
// count++;

final int sum = nums[i] + nums[j] + nums[k];
if (sum == 0) {
final ArrayList<Integer> integers = new ArrayList<>();

maxIndex = k;
break;
} else if (sum < 0) {
break;
}
}
}
}

return lists;
}```

```public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
Arrays.sort(nums); // 排序
int len = nums.length;
if(nums == null || len < 3) return ans;
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
while (L<R && nums[L] == nums[L+1]) L++; // 去重
while (L<R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}```

0 条评论

• ### 算法：优先队列-实战

这个arr数组要是比较小，可以直接用快速排序，再输出第K大的值。时间复杂度O(N*K*logk)

• ### 算法：递归和分治-实战

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### Java的基础程序设计结构（Java学习-1）

注释就是方便自己或者别人阅读代码，绝大多数的程序语言都有注释这个功能，大部分的注释命令都是相同的或者想通的，

• ### LeetCode第六天

第六天 30.(219) Contains Duplicate II ? JAVA class Solution { public boolean co...

• ### 2019 第十届蓝桥杯C/C++ 省赛B组题解

又是一年一度的蓝桥杯，这次也应该是我大学最后一次学科竞赛了，今年的省赛题型和往届有些不同，代码填空没有了，只有结果填空和编程大题，不过坑还是一样的多，稍不注意就...

• ### Leetcode Golang 27. Remove Element.go

版权声明：原创勿转 https://blog.csdn.net/anakinsun/article/details/88902476

• ### Leetcode Golang 162. Find Peak Element.go

版权声明：原创勿转 https://blog.csdn.net/anakinsun/arti...

• ### 每日算法系列【LeetCode 153】寻找旋转排序数组中的最小值

(例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2])。

• ### Leetcode 80 Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates": What if duplicates are allowed at most twic...