242. ********

思路：哈希表

哈希表是什么？哈希表又叫散列表。按我的理解，如果没学哈希表，我直接会拿字母的ASCII码做数组下标，也就是定义一个长度为123（z的ASCII码是122）的数组来计数，但是这样会浪费将近一百个空间。

所以，应该想办法把下标变小一些，充分利用数组，比如对26取余，使所有下标映射到0~25之间，这样只用定义长度为26的数组了。

这样通过映射把下标缩小范围而建立的数据结构是哈希表，映射规则（比如取余）叫哈希函数。

bool isAnagram(char* s, char* t) {
    int ls = strlen(s);
    int lt = strlen(t);
    if (ls != lt)
        return false;
    int a[30] = {0};
    for (int i = 0; i < ls; i++) {
        int key = s[i] % 26;
        a[key]++;
    }
    for (int i = 0; i < ls; i++) {
        int key = t[i] % 26;
        a[key]--;
        if (a[key] < 0)
            return false;
    }
    return true;
}

（上午做了个寻找数组中单独出现的数的题目，当时用的异或运算，这里一试不太行，如果s={aa}，t={bb}结果仍然是正确的）

349. 两个数组的交集

思路：set（C++）

(可是我写的是C啊！！！！！！！！<( ‵□′)>───Ｃε(┬﹏┬)3

所以这题变得和上一题没啥区别了━━(￣ー￣*|||━━

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size,
                  int* returnSize) {
    int a[1003] = {0}, *ans;
    int l = fmax(nums1Size, nums2Size);
    ans = (int*)malloc(sizeof(int) * 1000);
    int k = 0;
    for (int i = 0; i < l; i++) {
        if (i < nums1Size) {
            a[nums1[i]] = 1;
        }
    }
    for (int i = 0; i < l; i++) {
        if (i < nums2Size) {
            if (a[nums2[i]] == 1) {
                ans[k++] = nums2[i];
                a[nums2[i]] = 0;
            }
        }
    }
    *returnSize = k;
    return ans;
}

202. 快乐数（一点也不快乐）

思路

两种情况，要么最后得到1，要么最后陷入循环。

两种解法，方法一，哈希表记录历史情况，便于查找是否陷入循环（c语言写哈希表好不友好，什么set，map，都得手搓╰（‵□′）╯）

方法二，快慢指针，所有可能的sum（包括结果是1与陷入循环）可以相当于无形的链表，快慢指针进入链表后总会相遇，最后判断相遇值即可

int sum(int n) {
    int ans = 0;
    while (n != 0) {
        ans += pow(n % 10, 2);
        n /= 10;
    }
    return ans;
}
bool isHappy(int n) {
    int slow = n, fast = n;
    do {
        slow = sum(slow);
        fast = sum(sum(fast));
    } while (slow != fast);
    if (slow == 1)
        return true;
    return false;
}

1. 两数之和

思路

一、暴力

二、map结构（哈希）

暴力

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* a = malloc(sizeof(int) * 2);
    for (int i = 0; i < numsSize - 1; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] + nums[j] == target) {
                a[0] = i;
                a[1] = j;
                return a;
            }
        }
    }
    return a;
}

map（c语言造轮子）

（小题大做）（学c语言什么都要手搓/(ㄒoㄒ)/~~）

// 定义map节点的结构体
typedef struct map {
    int val;
    int key;
    struct map* next;
} mapnode;

#define HashSize 100    // 定义map大小
mapnode* Map[HashSize]; // 创建map，map节点的指针数组

// 实现创建节点
mapnode* create(int key, int val) {
    mapnode* pair = (mapnode*)malloc(sizeof(mapnode));
    pair->val = val;
    pair->key = key;
    pair->next = NULL;
    return pair;
}

// hash函数，实现映射，包括负数
int hash(int key) { return (key % HashSize + HashSize) % HashSize; }
// 插入新节点
void insert(int key, int val) {
    mapnode* pair = create(key, val);
    int index = hash(pair->key);
    if (Map[index] == NULL) {
        Map[index] = pair;
    } else {
        pair->next = Map[index];
        Map[index] = pair;
    }
    return;
}
void destoryMap(void) {
    for (int i = 0; i < HashSize; i++) {
        if (Map[i] != NULL) {
            mapnode* cur = Map[i];
            while (cur != NULL) {
                mapnode* temp = cur;
                cur = cur->next;
                free(temp);
            }
        }
    }
    return;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    *returnSize = 2;
    int* a = (int*)malloc(sizeof(int) * 2);
    memset(Map, 0, sizeof(Map));
    for (int i = 0; i < numsSize; i++) {
        int key = target - nums[i];
        int index = hash(key);
        if (Map[index] != NULL) {
            mapnode* pair = Map[index];
            while (pair != NULL) {
                if (pair->key == key && pair->val != i) {
                    a[0] = i;
                    a[1] = pair->val;
                    destoryMap();
                    return a;
                }
                pair = pair->next;
            }
        }
        insert(nums[i], i);
    }
    return NULL;
}

（时隔多日终于完成啦这一篇😭）

Day6||242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和