《LeetCode》—— LeetCode刷题日记

简介: 《LeetCode》—— LeetCode刷题日记

本期,我给大家讲述的是关于 n数之和这类题目的讲解,我会给大家讲解两数之和,三数之和和四数之和这三道题目。


(一)两数之和

链接如下:两数之和

题目如下:

 

题意分析:

要解决查找两个数字之和的问题,可以通过遍历数组并检查每个可能的数字对来使用暴力方法。然而,这种方法的时间复杂度为 O(n^2),效率不高。

💨 解决方法:

  1. 更好的方法是使用哈希表将数组的值存储为键,将其索引存储为值;
  2. 然后,对于数组中的每个数字,可以检查哈希表中是否存在目标总和与当前数字之间的差异;
  3. 如果存在,那么表示就已经找到了加起来等于目标总和的数字对。这种方法的时间复杂度为 O(n),效率更高。

具体步奏:

step 1:构建一个哈希表,用于记录各值和值对应的下标;

step 2:检查哈希表中是否存在目标总和与当前数字之间的差异:

  • 如果存在说明我们先前遍历的时候它出现过,根据记录的下标,我们返回两个数字的索引,就可以得到结果;
  • 如果没有,我们将当前数字及其索引添加到哈希表中

代码展示:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        vector <int> res;
        if (!size)
            return res;
        // 定义哈希表
        unordered_map<int, int> tmp;
        for (int i = 0; i < size; i ++) {
            if (tmp.find(target - nums[i]) != tmp.end()) 
            { 
                // find函数返回tmp.end()代表未找到,否则代表找到
                // 将结果存入数组
                res.push_back(tmp[target - nums[i]]);
                res.push_back(i);
                break;
            } 
            else 
            {
                tmp[nums[i]] = i; // 将未找到的值插入哈希表中,继续遍历
            }
        }
        return res;
    }
};

性能分析:

  • 时间复杂度:O(n),仅仅遍历数组一次,每次查询哈希表都是O(1)
  • 空间复杂度:O(n),最坏情况下找到数组结尾才找到,其他都加入哈希表,因此哈希表最长为n−1的长度

(二)三数之和

链接如下:三数之和

题目如下:

 

题意分析:

  1. 本题跟上述两数之和的题目类似。为了解决“三数之和”问题,我们可以使用两指针方法;
  2. 首先,我们按非降序对输入数组进行排序。然后,我们使用 for 循环遍历数组,对于每个元素,我们使用两个指针来查找另外两个元素,它们的总和为当前元素的负数;
  3. 如果我们找到这样的三元组,我们将其添加到我们的结果向量中。为了避免重复,我们跳过任何重复的元素。

具体步奏:

step 1我们对这个无序的数组进行排序操作,使用sort函数优先对其排序;

step 2:紧接着遍历该数组,对于三个数字都要判断是否相邻有重复的情况,因此要对其进行去重操作;

step 3:对于每个遍历到的元素假设它是三元组中最小的一个,那么另外两个一定在后面;

step 4:接下来,使用双指针的思想遍历去数组,因为最后得到的和为0,找到两个位置处的元素之和等于开始定义的最小值的相反值;

step 5:如果二者相加大于目标值,说明右指针太大了,那就将其左移缩小,相反如果二者相加小于目标值,说明左指针太小了,将其右移扩大,直到两指针相遇为止。

代码展示:

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 (i > 0 && nums[i] == nums[i-1]) 
                continue;
            //如果当前元素不是重复的,将目标值设置为当前元素的负值
            int target = -nums[i];
            //然后,将两个指针(左和右)分别初始化到向量中的下一个元素和最后一个元素。
            int left = i+1, right = nums.size()-1;
            //只要左小于右,该循环就会继续
            while (left < right) 
            {
                //检查左右值的总和是否等于目标值
                if (nums[left] + nums[right] == target) 
                {
                    //如果是,将三个值的向量添加到结果向量中
                    result.push_back({nums[i], nums[left], nums[right]});
                    //然后,向左递增,向右递减。
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (left < right && nums[right] == nums[right+1]) right--;
                } 
                //如果左侧和右侧的值之和小于目标值,则函数向左递增
                else if (nums[left] + nums[right] < target) 
                {
                    left++;
                } 
                //如果它大于目标值,则函数向右递减
                else 
                {
                    right--;
                }
            }
        }
        //最后,该函数返回包含所有唯一三元组的结果向量,这些三元组的总和为零
        return result;
    }
};

性能分析:

  • 时间复杂度:O(n^2),其中 n 是输入数组的长度。此实现使用两个嵌套循环遍历所有可能的数字对,并使用哈希表来检查数组中是否存在完成三元组所需的第三个数字,所以时间复杂度为O(n^2);
  • 空间复杂度:O(N)。

(三)四数之和

链接如下: 四数之和

题目如下:

 

题意分析:

同“三数之和”一样,如果通过遍历数组并检查每个可能的数字这种暴力方法,那么时间时间复杂度将达到O(N^4)。因此,还是跟上述一样整体思路是使用嵌套循环和两个指针来循环访问数组并查找四个元素。

题意涉及在数组中查找所有唯一的“四胞胎”,这些四胞胎的总和等于给定的目标值。

具体步奏:

step 1我们对这个无序的数组进行排序操作,使用sort函数优先对其排序;

step 2:注意这里因为是四个数,因此需要注意区间的变化情况;

step 3:紧接着遍历该数组,对于四个数字都要判断是否相邻有重复的情况,因此要对其进行去重操作;

step 4:接下来,使用双指针的思想遍历去数组,如果最后得到的和等于target,记录下来,但是四者中间的数字相加可能还会有;

step 5:如果四者相加大于目标值,说明右指针太大了,那就将其左移缩小,相反如果四者相加小于目标值,说明左指针太小了,将其右移扩大,直到两指针相遇为止。

代码展示:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> res;
    if (nums.empty()) 
        return res;
    //首先按升序对输入数组进行排序,这允许在迭代过程中有效地跳过重复值
    sort(nums.begin(), nums.end());
    int n = nums.size();
    //外部循环遍历四个数中的前三个整数
    for (int i = 0; i < n - 3; i++) 
    {
          if (i > 0 && nums[i] == nums[i - 1]) 
            continue;
        //内部循环访问第四个整数
        for (int j = i + 1; j < n - 2; j++) 
        {
           //去重
            if (j > i + 1 && nums[j] == nums[j - 1]) 
                continue;
            //双指针用于查找总和为目标值的其余两个整数
            int left = j + 1, right = n - 1;
            while (left < right) 
            {
                //检查总和是否等于目标值
               long sum =(long) nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) 
                {
                    res.push_back({nums[i], nums[j], nums[left], nums[right]});
                  
                    while (left < right && nums[left] == nums[left + 1]) left++;
                        left++;
                   
                    while (left < right && nums[right] == nums[right - 1]) right--;
                        right--;
                } 
                //和小于目标值,则函左指针向右
                else if (sum < target) 
                {
                    left++;
                } 
                //如果它大于目标值,则右指针向左
                else 
                {
                    right--;
                }
            }
        }
    }
    return res; 
    }
};

性能分析:

  • 时间复杂度:O(N^3),其中 n 是数组的长度。排序的时间复杂度是 O(nlogn),枚举四元组的时间复杂度是 O(N^3),所以时间复杂度为 O(N^3)
  • 空间复杂度: O(N),排序修改了输入数组 nums,实际情况中不一定允许这样的情况发生,因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序,空间复杂度为O(N)。

总体而言,由于嵌套循环,代码的时间复杂度为 O(n^3),但排序步骤降低了常数因子并提高了整体性能。


到此,便是以上题目的全部讲解。希望对大家有所帮助,感谢大家的阅读!!!

相关文章
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
52 6
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析,判断一棵树B是否是另一棵树A的子结构。
44 4
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
102 2
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
3月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
49 7
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码,确保min、push和pop操作的时间复杂度为O(1)。
24 4
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
49 5
|
3月前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
46 3
|
3月前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法,用以判断给定整数数组是否为某二叉搜索树的后序遍历结果,通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
21 3