今天刷题的时候，出现了一个问题。
今天刷的题是
这道题被leetcode定义为困难题，我第一眼想到的是先把L字符串数进行全排列，然后再用kmp字符串匹配算法对全排列后的字符串进行匹配，然后得出结果，然鹅细想发现，首先字符串的全排列算法一般用回溯法（然鹅回溯法并不是特别熟练），然后就是kmp算法了，这个算法有些难度，还是不太理解，所以最后还是放弃了，然后就想着看看别人写的算法能不能理解一下。
下面是别人给出的一个算法解，虽然这个算法可能并不是最优解，但是这个算法还是算比较容易理解吧，毕竟我能理解（我这个菜鸟都能理解相信大多数人还是可以理解的）。
public class Solution {
public List<Integer> findSubstring(String S, String[] L) {
List<Integer> ans = new ArrayList<Integer>();
if (S.length() < 1 || L.length < 1) return ans;
int len = L[0].length(); //题目说L中每个单词长度一样
//初始化HashMap，注意L中可能包含多个相同的字符串，所以用value表示个数
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (int j = 0; j < L.length; j++) {
if (map.containsKey(L[j])) {
map.put(L[j], map.get(L[j]) + 1);
} else {
map.put(L[j], 1);
}
}
//i的范围很关键，如果直接到S.length()是会超时的
for (int i = 0; i <= S.length() - L.length * len; i++) {
int from = i;
String str = S.substring(from, from + len);
int cnt = 0;
while (map.containsKey(str) && map.get(str) > 0) {
map.put(str, map.get(str) - 1);
cnt++;
from += len;
if (from + len > S.length()) break; //注意越界
str = S.substring(from, from + len);
}
//L中每个单词恰好出现一次，加入到结果集
if (cnt == L.length) {
ans.add(i);
}
//为下一次初始化HashMap
if (cnt > 0) {
map.clear();
for (int j = 0; j < L.length; j++) {
if (map.containsKey(L[j])) {
map.put(L[j], map.get(L[j]) + 1);
} else {
map.put(L[j], 1);
}
}
}
}
return ans;
}
}
还是说下他的算法思路吧，他首先建立一个HashMap，将字符串数组的每个字符串作为Map的键，将每个字符串出现的次数当作Map的值，然后遍历所要查找的字符串S，由于L字符串数组中的字符串长度都固定，所以遍历的时候直接截取字符串，然后看map中是否存在K为所截取的字符串，如果存在且该字符串键所对应的值不为0，则让次数减一，一直遍历到字符串末尾，一次循环完后判断存在键的数量是否等于字符串数组的长度，若相等则说明S存在L字符串数组组合的字符串，进行下次循环之前得重新给HashMap赋值，这就是问题所在了，由于他的赋值时像初始化一样先清空HashMap，然后依次添加键值对，这时候我处女座的强迫症就犯了，为啥他不定义一个临时的HashMap，将原始的HashMap赋值给临时HashMap不就行了嘛，为何要这么麻烦。。。。然后我就自作主张，建立了一个临时HashMap，每次循环完以后直接将原始的HashMap赋值给临时HashMap，然鹅出事了，
我就只是将他的清空map，然后依次添加键值对换成了建立临时map，然后再原始map赋值给临时map，结果居然就变了，真的想不明白，突然想到了以前遇到的一个问题也是很类似，是一个字符串数组赋值给另外一个字符串数组时遇到的，赋值完以后两个字符串像是绑定了一样，一个字符串数组变了另一个字符串数组也跟着变了，其实这种赋值只是将其对象的引用指向了和赋值对象相同的那个对象，所以他们所指向的引用地址就变成一样的了，当改变其中之一时就会改变所有指向该引用的变量。由这个我就想到了应该是这种赋值的时候只是将它们的引用指向了同一个，所以最后改变的时候两个都会改变。然后说说我的解决办法吧，一开始准备用clone()方法，可是hashmap里面没有clone()方法，因此只有先新建一个临时hashmap，然后用putAll()方法将原始的hashmap整个添加进去。