class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        /*
         需要修改原始数据 vector<int>& nums
         只读取数据，不修改 const vector<int>& nums 
         需要原始数据的独立副本（罕见） vector<int> nums（值传递）
         unordered_map<int, int> hashtable; # 构建一个哈希表，key是数值，value是索引
        */
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]); // auto自动判断类型
            if (it != hashtable.end()) { // 没找到返回 end() 迭代器
                return {it->second, i}; // 通过 it->second 获取哈希表中存储的索引
            }
            hashtable[nums[i]] = i; // 由于只有唯一答案，在寻找后将元素加入
        }
        return {};
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp; // 构造一个哈希表用于记录前缀和出现的次数
        int count = 0; // 用于记录当前的前缀和
        int ans = 0; 
        for(int i =  0; i < nums.size(); i++){
            mp[count]++; // 记录当前位置前缀和的数量
            count += nums[i];
            if(mp.find(count - k) != mp.end()){ // 查找是否存在从某个位置到当前位置和为K
                ans += mp[count - k]; // 加上满足该条件前缀和的数量
            }
        }
        return ans;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> maxNow(nums.size()); // 初始化一个动态数组，用于记录以i结尾的最大子数组和
        maxNow[0] = nums[0]; // 由于后面有用上 i-1 这里要进行初始化
        int ansMax = nums[0]; // 遍历一遍找到最大的值
        for(int i = 1; i < nums.size();i++){
            maxNow[i] = max(nums[i] + maxNow[i-1], nums[i]); // 确定是否要加上前面的部分
            ansMax = max(ansMax, maxNow[i]);
        }
        return ansMax;
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int col = matrix.size();
        int row = matrix[0].size();
        vector<bool> col_zero(col, false); // 用于记录有0的行
        vector<bool> row_zero(row, false); // 用于记录有0的列
        for(int i = 0; i < col; i++){
            for(int j = 0; j < row; j++){
                if(matrix[i][j] == 0){
                    col_zero[i] = row_zero[j] = 1;
                }
            }
        }
        for(int i = 0; i < col; i++){
            for(int j = 0; j < row; j++){
                if(col_zero[i] ==1 || row_zero[j] == 1){
                    matrix[i][j] = 0;
                }
            }
        } 
        
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode { // 自定义的链表
 *     int val; 
 *     ListNode *next; // *是地址指示符，表示这里的next为一个ListNode类型的指针
 *     ListNode(int x) : val(x), next(NULL) {} // 构造函数，若还有next参数，eg: ListNode(6， next)
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode *> set; // 定义一个哈希表用于存地址，unordered_set用于储存唯一元素
        ListNode *temp = headA; // temp是一个地址，*是在定义中起到一个标识的作用
        while(temp != NULL){ // 在定义外使用不用加*，表示的仍然为一个地址，加上*反而是表示该地址对应的数据
            set.insert(temp); // unordered_set增加元素用insert()方法
            temp = temp->next; // ->是成员访问运算符，用于通过指针访问对象的成员（变量或函数），等价于先对指针解引用（*），再用点号（.）访问成员
        } 
        temp = headB;
        while(temp != NULL){
            if(set.find(temp) != set.end()){
                return temp;
            }
            temp = temp -> next;
        }
        return {};
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* backward = nullptr; // 第一个元素要指向NULL，因此反向链表先初始化一个NULL
        ListNode *forwoard;
        while(cur != nullptr){
            forwoard = cur -> next; // 对于forward的定义是正向链表当前位置的下一个元素
            cur -> next = backward; // 将当前位置next反向
            backward = cur; // 沿正向方向移动
            cur = forwoard; // 沿正向方向移动
        }
        return backward;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

 // 方法一：将值复制到数组中后用双指针法
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *temp = head;
        vector<int> nodeVal; // 记录下链表中所有的值
        while(temp != nullptr){
            nodeVal.push_back(temp->val);
            temp = temp->next;
        }
        for(int i = 0; i < nodeVal.size(); i++){
            if(nodeVal[i] != nodeVal[nodeVal.size()-1-i]){ // 双指针检测
                return false;
            }
        }
        return true;
    }
};

// 方法二：递归
class Solution {
    ListNode *front; // 定义一个全局的front
public:
    bool recursively(ListNode *back){
        if(back != nullptr){ // 当深入到链表最后一个节点时递归终止
            if(!recursively(back->next)){ // 递归的核心
                return false; // 回溯时若出现不匹配的直接false，然后会一层层上传至退出
            }
            if(front->val != back->val){ // 比较前后指针
                return false;
            }
            front = front->next;
        }

        return true;   // 两重作用：1.递归到最后一层返回true，从而开始比较 2.在每一层前后比较相同时返回true
    }

    bool isPalindrome(ListNode* head) {
        front = head;
        ListNode *back = head;
        return recursively(back);
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode *> set; // 创建一个用于存储节点地址的哈希表
        ListNode *temp = head;
        while(temp != NULL){
            if(set.find(temp) != set.end()){
                return true;
            }
            set.insert(temp);
            temp = temp->next;
        }
        return false;
    }
};