当前位置：首页 > news >正文

【Leecode 随笔】

news 2025/8/10 7:47:13

文章目录

- 题目一：三数之和（LeetCode 15）
- - 题目分析：
  - 解题思路：
  - 示例代码：
  - 代码解析：
- 题目二：无重复字符的最长子串（LeetCode 3）
- - 题目分析：
  - 解题思路：
  - 示例代码：
  - 代码解析：
- 题目三：盛最多水的容器（LeetCode 11）
- - 题目分析：
  - 解题思路：
  - 示例代码：
  - 代码解析：

🌈你好呀！我是山顶风景独好
🎈欢迎踏入我的博客世界，能与您在此邂逅，真是缘分使然！😊
🌸愿您在此停留的每一刻，都沐浴在轻松愉悦的氛围中。
📖这里不仅有丰富的知识和趣味横生的内容等您来探索，更是一个自由交流的平台，期待您留下独特的思考与见解。🌟
🚀让我们一起踏上这段探索与成长的旅程，携手挖掘更多可能，共同进步！💪✨

题目一：三数之和（LeetCode 15）

题目分析：

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

解题思路：

排序数组：先对数组进行排序，便于去重和双指针操作。
固定一个元素：遍历数组，固定三元组中的第一个元素 nums[i]。
双指针查找：对于每个固定的 i，使用左右双指针（left = i+1，right = 数组末尾）寻找 nums[left] + nums[right] = -nums[i]。
去重处理：在遍历和移动指针过程中，通过跳过相同元素避免重复三元组。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  // 比较函数，用于qsort排序
int compare(const void *a, const void *b) {return *(int*)a - *(int*)b;
}// 函数声明
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {// 排序数组qsort(nums, numsSize, sizeof(int), compare);// 分配结果空间int** result = (int**)malloc(sizeof(int*) * 20000);*returnColumnSizes = (int*)malloc(sizeof(int) * 20000);*returnSize = 0;for (int i = 0; i < numsSize - 2; i++) {// 去重：跳过相同的第一个元素if (i > 0 && nums[i] == nums[i-1]) continue;int left = i + 1;int right = numsSize - 1;int target = -nums[i];while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {// 找到符合条件的三元组result[*returnSize] = (int*)malloc(sizeof(int) * 3);result[*returnSize][0] = nums[i];result[*returnSize][1] = nums[left];result[*returnSize][2] = nums[right];(*returnColumnSizes)[*returnSize] = 3;(*returnSize)++;// 去重：跳过相同的left和right元素while (left < right && nums[left] == nums[left+1]) left++;while (left < right && nums[right] == nums[right-1]) right--;left++;right--;} else if (sum < target) {left++;} else {right--;}}}return result;
}int main() {int nums[] = {-1, 0, 1, 2, -1, -4};int numsSize = 6;int returnSize;int* returnColumnSizes;int** result = threeSum(nums, numsSize, &returnSize, &returnColumnSizes);printf("ThreeSum results:\n");for (int i = 0; i < returnSize; i++) {printf("[%d, %d, %d]\n", result[i][0], result[i][1], result[i][2]);free(result[i]);}free(result);free(returnColumnSizes);return 0;
}

代码解析：

通过qsort对数组排序，为双指针操作和去重奠定基础。
外层循环固定三元组的第一个元素，通过i>0时跳过与前一个元素相同的值实现去重。
内层使用双指针查找满足条件的另外两个元素，当三数之和为0时，记录结果并通过移动指针跳过相同元素实现去重。
时间复杂度O(n²)，空间复杂度O(1)（不考虑结果存储）。

题目二：无重复字符的最长子串（LeetCode 3）

题目分析：

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。例如：输入"abcabcbb"，输出3（最长子串为"abc"）；输入"bbbbb"，输出1（最长子串为"b"）。

解题思路：

滑动窗口：使用左右指针维护一个无重复字符的窗口 [left, right]。
哈希表：记录字符最后出现的索引，用于快速判断字符是否在当前窗口中。
扩展窗口：right指针向右移动，若字符不在窗口中则加入哈希表。
收缩窗口：若字符已在窗口中，则将left指针移动到该字符上次出现位置的右侧。
更新长度：每次移动right指针时，计算当前窗口长度并更新最大长度。

示例代码：

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>  #define MAX_CHAR 128int lengthOfLongestSubstring(char * s) {int lastOccurrence[MAX_CHAR];memset(lastOccurrence, -1, sizeof(lastOccurrence));int maxLen = 0;int left = 0;int len = strlen(s);for (int right = 0; right < len; right++) {char c = s[right];// 如果字符已出现且在当前窗口内，则移动left指针if (lastOccurrence[c] != -1 && lastOccurrence[c] >= left) {left = lastOccurrence[c] + 1;}// 更新字符最后出现位置lastOccurrence[c] = right;// 计算当前窗口长度并更新最大长度int currentLen = right - left + 1;if (currentLen > maxLen) {maxLen = currentLen;}}return maxLen;
}int main() {char s1[] = "abcabcbb";printf("Length of longest substring in \"%s\": %d\n", s1, lengthOfLongestSubstring(s1));char s2[] = "bbbbb";printf("Length of longest substring in \"%s\": %d\n", s2, lengthOfLongestSubstring(s2));char s3[] = "pwwkew";printf("Length of longest substring in \"%s\": %d\n", s3, lengthOfLongestSubstring(s3));return 0;
}

代码解析：

使用大小为128的数组lastOccurrence记录每个ASCII字符最后出现的索引，初始化为-1表示未出现。
right指针遍历字符串，对于每个字符，若已在当前窗口（lastOccurrence[c] >= left），则将left移动到该字符上次出现位置+1。
每次更新字符最后出现位置，并计算当前窗口长度，更新最大长度。
时间复杂度O(n)（n为字符串长度），空间复杂度O(1)（固定大小的字符数组）。

题目三：盛最多水的容器（LeetCode 11）

题目分析：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。

解题思路：

双指针：初始化left指针在数组起始位置，right指针在数组末尾。
计算面积：容器的水量由短板高度和两板距离决定，即面积 = min(height[left], height[right]) * (right - left)。
移动指针：为了寻找更大的面积，移动高度较小的指针（因为移动高指针只会减小宽度，而移动低指针可能找到更高的板）。
更新最大值：每次计算面积后与当前最大值比较，保留较大值。

示例代码：

#include <stdio.h>  
#include <stdlib.h>  int maxArea(int* height, int heightSize) {int left = 0;int right = heightSize - 1;int maxWater = 0;while (left < right) {// 计算当前容器的水量int width = right - left;int currentHeight = (height[left] < height[right]) ? height[left] : height[right];int currentWater = width * currentHeight;// 更新最大水量if (currentWater > maxWater) {maxWater = currentWater;}// 移动较矮的指针if (height[left] < height[right]) {left++;} else {right--;}}return maxWater;
}int main() {int height1[] = {1,8,6,2,5,4,8,3,7};int size1 = sizeof(height1) / sizeof(height1[0]);printf("Max water for [1,8,6,2,5,4,8,3,7]: %d\n", maxArea(height1, size1));int height2[] = {1,1};int size2 = sizeof(height2) / sizeof(height2[0]);printf("Max water for [1,1]: %d\n", maxArea(height2, size2));return 0;
}