链表 — 环形链表

题目链接：142. 环形链表 II - 力扣（LeetCode）

题目要求：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例：

输入：head = [3,2,0,-4] , pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

**思路：**判断是否有环（快慢指针，看它们是否会相遇），找到环的入口节点（设置两个指针，一个从相遇位置向前移动，一个从头节点开始移动，两者会在环的入口节点处相遇）

解法：

• C

struct ListNode *detectCycle(struct ListNode *head) {
    typedef struct ListNode ListNode;
    ListNode* fast = head;
    ListNode* slow = head;
    while(fast && fast->next){
        fast = fast->next->next;    // 快指针一次向后移动两步
        slow = slow->next;          // 慢指针一次向后移动一步
        if(fast == slow){           // 存在环
            ListNode* tmp1 = head;
            ListNode* tmp2 = fast;
            while(tmp1 != tmp2){
                tmp1 = tmp1->next;
                tmp2 = tmp2->next;
            }
            return tmp1;
        }    
    }
    return NULL;
}

• C++

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next !=NULL){
            fast = fast->next->next;    // 快指针一次移动两个节点
            slow = slow->next;          // 慢指针一次移动一个节点
            while(fast == slow){
                ListNode* begin = head;   // 一个节点从起点开始
                ListNode* end   = fast;   // 一个节点从相遇的点开始
                while(begin != end){
                    begin = begin->next;
                    end = end->next;
                }
                return end;
            }
        }
        return NULL;
    }
};

哈希表 — 有效的字母异位词

题目链接：242. 有效的字母异位词 - 力扣（LeetCode）

**题目要求：**给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例：

输入: s = "anagram", t = "nagaram"
输出: true

输入: s = "rat", t = "car"
输出: false

**思路：**遍历第一个字符串，使用数组统计每一个字符出现的频率，遍历第二个字符串，字符每出现一次，频率 -1，判断数组是否每一项都为 0

解法：

• C

bool isAnagram(char* s, char* t) {
    int len_s = strlen(s);
    int len_t = strlen(t);
    if(len_s != len_t)     // 如果长度不行等直接返回 false
        return false;
    int tmp[26] = {0};
    int i;
    for(i = 0; i < len_s; i++){
        tmp[s[i] - 'a']++;
    }
    for(i = 0; i < len_t; i++){
        tmp[t[i] - 'a']--;
    }
    for(i = 0; i < 26; i++){
        if(tmp[i] != 0)      // 如果有一项不等于0，则返回 false    
            return false;
    }
    return true;
}

• C++

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size()){
            return false;
        }
        int tmp[26];
        for(int i = 0; i < s.size(); i++){
            tmp[s[i] - 'a']++;
        }
        for(int j = 0; j < t.size(); j++){
            tmp[t[j] - 'a']--;
        }
        for(int k = 0; k < 26; k++){
            if(tmp[k])
                return false;
        }
        return true;
    }
};

哈希表 — 两个数组的交集

题目链接：349. 两个数组的交集 - 力扣（LeetCode）

题目要求：给定两个数组nums1和nums2，返回 它们的 交集 ，输出结果中的每个元素一定是唯一的，我们可以不考虑输出结果的顺序。

示例：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

**思路：**哈希表使用数组，遍历第一个数组，将出现的值对应的哈希数组项设为1，遍历第二个数组，如果值对应的哈希数组项为1，则这个值出现过

解法：

• C（使用数组作为哈希表，但是数组中的值必须介于 0~1000 之间，局限性太大）

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int map[1001] = {0};       // 给定数组中值的大小：0 ~ 1000 
    int min = nums1Size < nums2Size ? nums1Size : nums2Size;
    int* result = (int*)malloc(sizeof(int) * min);    
    int i, k = 0;
    for(i = 0; i < nums1Size; i++){
        map[nums1[i]] = 1;
    }
    for(i = 0; i < nums2Size; i++){
        if(map[nums2[i]] == 1){
            map[nums2[i]] = 0;         // 每个数据只写入一次
            result[k++] = nums2[i];             
        }
    }
    *returnSize = k;
    return result;
}

• C++（使用 set）

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;   // 往unordered_set中放入元素有自动去重功能
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for(int num : nums2){   // 遍历 nums2 数组
            if(nums_set.find(num) != nums_set.end()){   
                result_set.insert(num);  // 如果能找到对应元素，则代表重复
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

哈希表 — 两数之和

题目链接：1. 两数之和 - 力扣（LeetCode）

题目要求：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。（多个答案返回一个）

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

**思路：**C：两层 for 循环

C++：使用 map 保存元素的数值（key）以及它所对应的下标（value），注意（map 中所保存的是已经遍历过的元素），每到数组中的一项，就查找 map 看是否有曾经的元素加上现在数组项的值等于 target

• C

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int tmp = 0;
    int* result = (int*)malloc(sizeof(int)*2);
    for(int i = 0; i < numsSize; i++){
        tmp = nums[i];
        result[0] = i; 
        for(int j = 0; j < numsSize; j++){
            if(tmp + nums[j] == target){
                if(i != j){              // 避免返回的两个下标结果相同
                    result[1] = j;
                    *returnSize = 2;
                    return result;                    
                }
            }
        }
    }
    return NULL;
}

• C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;   // 创建map容器，存放遍历过的元素，以及它所对应的下标
        for(int i = 0; i < nums.size(); i++){
            int num = target - nums[i];
            auto index = map.find(num);
            if(index != map.end()){   // 之前的元素存在相加等于 target的
                return {index->second, i};
            }
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};

哈希表 — 四数相加II

题目链接：454. 四数相加 II - 力扣（LeetCode）

题目要求：

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

**思路：**遍历A和B数组，统计两个数组元素之和，和出现的次数，放到map中，再遍历C和D数组，找到如果 0-(c+d) 在map中出现过的话，就用 result 把 map 中 key 对应的 value 统计出来

解法：

• C++

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map;
        for(int m : nums1){
            for(int n : nums2){
                map[m + n]++;
            }
        }
        int result = 0;
        for(int i : nums3){
            for(int j : nums4){
                if(map.find(0 - (i + j)) != map.end()){
                    result += map[0 - (i + j)];
                }
            }
        }
        return result;
    }
};

哈希表 — 三数之和

题目链接：15. 三数之和 - 力扣（LeetCode）

题目要求：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

**思路：**虽然可以使用哈希法解决（方法与四数相加差不多，但是需要进行去重，这就比较麻烦），这里使用双指针法

解法：

• C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());   // 先对整个数组进行排序（从小到大）
        for (int i = 0; i < nums.size(); i++) {   
            if (nums[i] > 0) {           // 如果第一个数就大于零，就不可能存在还有两个数与它相加等于零
                return result;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {   // 对第一个数进行去重操作
                continue;
            }                               // 第一个指针从左开始，第二个指针从右开始
            int left = i + 1;               // 指向第二个数的指针
            int right = nums.size() - 1;    // 指向第三个数的指针
            while (right > left) {          
                if (nums[i] + nums[left] + nums[right] > 0){
                     right--;
                }else if (nums[i] + nums[left] + nums[right] < 0){
                     left++;
                }else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    while (right > left && nums[right] == nums[right - 1]) right--;   // 第三个数的去重操作 
                    while (right > left && nums[left] == nums[left + 1]) left++;      // 第二个数的去重操作
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

哈希表 — 四数之和

题目链接：18. 四数之和 - 力扣（LeetCode）

题目要求：

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

**思路：**延续了三数之和的思路，多使用一层for循环（时间复杂度 O(n^3) ）

解法：

• C++

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());   // 对整个数组进行排序（从小到大）
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] > target && nums[i] >= 0){   // 两个负数相加，值会越来越小(一级剪枝)
                break;
            }
            if(i > 0 && nums[i] == nums[i - 1]){   // 去重操作
                continue; 
            }
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] + nums[j] > target && nums[i] + nums[j] >=0){   // 二级剪枝操作
                    break;
                }
                if(j > i + 1 && nums[j] == nums[j - 1]){   // 去重操作
                    continue;
                }
                int left  = j + 1;               // 其余两个数进行双指针操作
                int right = nums.size() - 1;
                while(left < right){
                    // 如果不加 long 的话，结果会溢出
                    if((long) nums[i] + nums[j] + nums[left] + nums[right] > target){
                        right--;
                    }else if((long) nums[i] + nums[j] + nums[left] + nums[right] < target){
                        left++;
                    }else{
                        result.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                        while (right > left && nums[right] == nums[right - 1]) right--;   
                        while (right > left && nums[left] == nums[left + 1]) left++;     
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
};

字符串 — 反转字符串I

题目链接：344. 反转字符串 - 力扣（LeetCode）

**题目要求：**编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

**思路：**双指针（一个指向头部，一个指向尾部，进行数据的交换）

解法：

• C

void reverseString(char* s, int sSize) {
    int left = 0;
    int right = sSize - 1;
    while(left < right)
    {
        char str = s[left];
        s[left++] = s[right];
        s[right--] = str;
    }
}

• C++

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size() - 1; i < s.size() / 2; i++, j--){
            swap(s[i], s[j]);   // swap 交换两个变量的值
        }      
    }
};

字符串 — 反转字符串II

题目链接：541. 反转字符串 II - 力扣（LeetCode）

题目要求：

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

**思路：**每一次 for 循环 += 2，计算剩余字符串的长度，从而得知要翻转的字符个数

解法：

• C

char* reverseStr(char* s, int k) {
    int len = strlen(s);
    for(int i = 0; i < len; i += (2 * k)){
        // 剩余字符串的长度，不足k时设为剩余的字符串长度，大于k时设为k
        int num = i + k > len ? len - i : k;
        if(num){
            int left  = i;
            int right = i + num - 1;
            while(left < right){
                char tmp = s[left];
                s[left++] = s[right];
                s[right--] = tmp;
            }
        }
    }
    return s;
}

• C++

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            if (i + k <= s.size()) {
                reverse(s.begin() + i, s.begin() + i + k ); // 反转前k个字符
            } else {
                reverse(s.begin() + i, s.end()); // 全部反转
            } 
        }
        return s;
    }
};

字符串 — 反转字符串里的单词

题目链接：151. 反转字符串中的单词 - 力扣（LeetCode）

题目要求：

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

**思路：**先对字符串进行整体的反转，再对每一个单词进行反转

解法：

• C

//反转字符串中的指定范围
void reverse(char* s, int start, int end) {
    for(; start < end; ){
        char tmp = s[start];
        s[start++] = s[end];
        s[end--] = tmp;
    }
}

// 删除字符串两端和中间多余的空格
void removeExtraSpace(char* s) {
    int start = 0;
    int end = strlen(s) - 1;
    int index = 0;      // 新字符串的实时下标
    while(s[start] == ' ') start++;   // 去除开头多余的字符
    while(s[end] == ' ') end--;       // 去除结尾多余的字符
    for(int i = start; i <= end; i++){
        if(s[i] == ' ' && s[i+1] == ' '){
            continue;      // 这个字符不做处理
        }
        s[index] = s[i];   // 将这个字符写入新的字符串中
        index++;
    }
    s[index] = '\0';
}

char* reverseWords(char* s) {
    int strstart = 0;
    removeExtraSpace(s);     // 先删除多余的空格
    reverse(s, 0, strlen(s) - 1);  // 将整个字符串进行反转
    for(int strend = 0; strend <= strlen(s); strend++){
        if(s[strend] == ' ' || s[strend] == '\0'){    // '\0':对最后一个单词进行反转
            reverse(s, strstart, strend - 1);     // 对这个范围的字符串进行反转
            strstart = strend + 1;
        } 
    }
    return s;
}

• C++

class Solution {
public:
    void reverse(string& s, int start, int end){ // 反转字符串
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string& s) {
        int slow = 0; 
        for (int i = 0; i < s.size(); i++) { 
            if (s[i] != ' ') {  // 去除开头的空格
                if (slow != 0) s[slow++] = ' ';   // 为每一个完整的单词后面加上空格
                while (i < s.size() && s[i] != ' ') {  // 获取一个完成的单词
                    s[slow] = s[i];
                    i++;
                    slow++;
                }
            }
        }
        s.resize(slow);  // 改变字符串容器的大小
    }

    string reverseWords(string s) {
        removeExtraSpaces(s); // 为字符串去除多余的空格
        reverse(s, 0, s.size() - 1); // 反转整体的字符串
        int start = 0; 
        for (int i = 0; i <= s.size(); i++) {
            if (i == s.size() || s[i] == ' ') { 
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        return s;
    }
};