力扣第242题-有效的字母异位词1.本题考点为哈希表比较容易想到完整代码如下1. bool isAnagram(char* s, char* t) { 2. // 创建26个字母的计数数组初始全0 3. int hash[26] {0}; 4. // 获取两个字符串长度 5. int len1 strlen(s), len2 strlen(t); 6. // 长度不同一定不是字母异位词直接返回false 7. if (len1 ! len2) return false; 8. 9. // 遍历s对应字母计数1 10. for (int i 0; i len1; i){ 11. hash[s[i] - a]; 12. } 13. // 遍历t对应字母计数-1 14. for (int i 0; i len2; i){ 15. hash[t[i] - a]--; 16. // 某个字母负数说明t该字母更多直接false 17. if (hash[t[i] - a] 0) return false; 18. } 19. 20. // 全部抵消完毕是字母异位词 21. return true; 22. }该算法时间复杂度为O(n)空间复杂度为O(1)。力扣第349题-两个数组的交集1.本题也是考察哈希表只需要为两个数组各创建一个哈希数组记录哪些数字出现了最后在对比两个哈希数组即可。完整代码如下1. int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) { 2. // 哈希数组题目数据范围0~1000分别记录两个数组数字出现标记 3. int hash1[1001] {0}; 4. int hash2[1001] {0}; 5. // cnt记录交集元素个数 6. int cnt 0; 7. // 分配结果数组最多存1001个不同数字 8. int* res (int*)malloc(sizeof(int) * 1001); 9. 10. // 遍历nums1标记出现过的数字 11. for (int i 0; i nums1Size; i){ 12. hash1[nums1[i]]; 13. } 14. // 遍历nums2标记出现过的数字 15. for (int i 0; i nums2Size; i){ 16. hash2[nums2[i]]; 17. } 18. // 遍历0~1000全部数字两边都出现过则加入交集 19. for (int i 0; i 1001; i){ 20. if (hash1[i] 0 hash2[i] 0){ 21. res[cnt] i; 22. } 23. } 24. 25. // 设置返回数组长度 26. *returnSize cnt; 27. return res; 28. }该算法时间复杂度为O(m n)空间复杂度为O(1)常数空间的哈希数组。2.还可以做进一步优化两个哈希数组合并为一个结果数组的开辟空间大小设定为两个数组大小的较小值。完整代码如下1. int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) { 2. // 哈希数组数值范围0~1000标记nums1中出现过的数字 3. int hash[1001] {0}; 4. // 统计交集元素数量 5. int cnt 0; 6. // 交集最多元素个数等于较短数组长度以此分配结果数组内存 7. int lessSize nums1Size nums2Size ? nums1Size : nums2Size; 8. int* res (int*)malloc(sizeof(int) * lessSize); 9. 10. // 遍历nums1仅将首次出现的数字标记为1去重 11. for (int i 0; i nums1Size; i){ 12. if (hash[nums1[i]] 0){ 13. hash[nums1[i]]; 14. } 15. } 16. // 遍历nums2找到哈希表中标记过的数字即为交集 17. for (int i 0; i nums2Size; i){ 18. if (hash[nums2[i]] 0){ 19. res[cnt] nums2[i]; 20. hash[nums2[i]]--; // 减1避免重复存入相同元素 21. } 22. } 23. 24. // 赋值返回数组有效长度 25. *returnSize cnt; 26. return res; 27. }该算法时间复杂度为O(m n)空间复杂度为O(1)常数空间的哈希数组。