LeetCode---哈希表

242. 有效的字母异位词

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

代码示例: 

//时间复杂度: O(n)
//空间复杂度: O(1)
class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26] = {0};
        for (int i = 0; i < s.size(); i++) {
            // 并不需要记住字符a的ASCII,只要求出一个相对数值就可以了
            hash[s[i] - 'a']++;
        }
        for (int i = 0; i < t.size(); i++) {
            hash[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (hash[i] != 0) {
                // record数组如果有的元素不为零0,说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0,说明字符串s和t是字母异位词
        return true;
    }
};

 349. 两个数组的交集

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

代码示例1:(set) 

//时间复杂度: O(n + m) m 是最后要把 set转成vector
//空间复杂度: O(n)
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果,之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {//若找到,返回该键的元素的迭代器;若没找到,返回set.end();
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

本题后面 力扣改了 题目描述 和 后台测试数据,增添了 数值范围:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

所以就可以 使用数组来做哈希表了, 因为数组都是 1000以内的。

代码示例2:(数组)  

//时间复杂度: O(m + n)
//空间复杂度: O(n)
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果,之所以用set是为了给结果集去重
        int hash[1005] = {0}; // 默认数值为0
        for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
            hash[num] = 1;
        }
        for (int num : nums2) { // nums2中出现话,result记录
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

1. 两数之和

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

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

代码示例1:(暴力解法)  

//时间复杂度:O(n^2),因为在最坏情况下需要检查所有的 n(n-1)/2 对组合。
//空间复杂度:O(1),除了存储结果的向量外,不需要额外的空间。
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        for(int i = 0;i < nums.size();i++){
            for(int j = i+1;j<nums.size();j++){
                if((nums[i] + nums[j]) == target){
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
        // 如果没有找到满足条件的结果,返回空结果
        return result;
    }
};

 代码示例2:(map)  

//时间复杂度: O(n)
//空间复杂度: O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++) {
            // 遍历当前元素,并在map中寻找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果没找到匹配对,就把访问过的元素和下标加入到map中
            map.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};

454. 四数相加II 

给你四个整数数组 nums1nums2nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:

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

代码示例: 

//时间复杂度: O(n^2)
//空间复杂度: O(n^2),最坏情况下A和B的值各不相同,相加产生的数字个数为 n^2
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> umap; //key:a+b的数值,value:a+b数值出现的次数
        // 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中
        for (int a : A) {
            for (int b : B) {
                umap[a + b]++;    //与题242的思路一致
            }
        }
        int count = 0; // 统计a+b+c+d = 0 出现的次数
        // 在遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话,就把map中key对应的value也就是出现次数统计出来。
        for (int c : C) {
            for (int d : D) {
                if (umap.find(0 - (c + d)) != umap.end()) {
                    count += umap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

15. 三数之和 

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

代码示例: 

//时间复杂度: O(n^2)
//空间复杂度: O(1)
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.size(); i++) {
            // 排序之后如果第一个元素已经大于零,那么无论如何组合都不可能凑成三元组,直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            // 错误去重a方法,将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            // 正确去重a方法
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.size() - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里,0,0,0 的情况,可能直接导致 right<=left 了,从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) 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]});
                    // 去重逻辑应该放在找到一个三元组之后,对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    // 找到答案时,双指针同时收缩
                    right--;
                    left++;
                }
            }

        }
        return result;
    }
};

18. 四数之和 

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

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

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

代码示例: 

//时间复杂度: O(n^3)
//空间复杂度: O(1)
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break,统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对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;
    }
};

 参考如下:

代码随想录

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/670662.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【NOIP提高组】进制转换

【NOIP提高组】进制转换 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 我们可以用这样的方式来表示一个十进制数&#xff1a;将每个阿拉伯数字乘以一个以该数字所处位置的&#xff08;值减1&#xff09;为指数&#xff0c;以 10 为底数的幂…

Java web应用性能分析之【java进程问题分析概叙】

Java web应用性能分析概叙-CSDN博客 Java web应用性能分析之客户端慢_有的客户端跑java应用特别慢-CSDN博客 Java web应用性能分析服务端慢之前端页面慢_前端页面加载性能分析-CSDN博客 Java web应用性能分析服务端慢之Nginx慢_前端nginx请求比直接连接后台慢很多-CSDN博客 …

【安规介绍】

文章目录 一、基础知识安规上的六类危险的防护&#xff1a;安全电压漏电流接触电流能量问题&#xff1a;火灾问题&#xff1a;热问题结构问题阻燃等级绝缘等级&#xff1a;对接地系统的要求&#xff1a;结构要求:电气要求&#xff1a; 二、设计的关键电气绝缘距离电气爬电距离:…

四足机器人步态仿真(三)四足机器人基础步态仿真

观前提醒&#xff0c;本章主要内容为分析四足机器人步态实现和姿态控制&#xff0c;碰撞体积等程序 步态效果&#xff1a; 一、完整代码如下 # -*- coding: utf-8 -*-import pybullet as pimport timeimport numpy as npp.connect(p.GUI)p.createCollisionShape(p.GEOM_PLANE…

插入排序(直接插入排序、折半插入排序、希尔排序)的性能分析

目录 前言 插入排序 直接插入排序性能分析 折半插入排序性能分析 希尔排序性能分析 前言 本篇文章主要是总结插入排序的性能分析&#xff0c;具体的概念、算法、排序过程&#xff0c;我前面的文章有写&#xff0c;在这里就不再过多赘述了。 插入排序 插入排序是一种简单直…

MYSQL数据库细节详细分析

MYSQL数据库的数据类型(一般只需要用到这些) 整型类型&#xff1a;用于存储整数值&#xff0c;可以选择不同的大小范围来适应特定的整数值。 TINYINTSMALLINTMEDIUMINTINTBIGINT 浮点型类型&#xff1a;用于存储带有小数部分的数值&#xff0c;提供了单精度&#xff08;FLOA…

2-1RT-Thread线程管理-笔记

2-1RT-Thread线程管理-笔记 其中系统线程由内核创建&#xff0c;如main函数和空闲线程都属于系统线程&#xff0c;而用户线程是由应用程序所创建的。 对于资源较大的MCU可以适当设计较大的线程栈&#xff0c;也可以在初始化时设置一个具体的数值&#xff0c;如1K或2K字节。…

【JavaEE 进阶(二)】Spring MVC(下)

❣博主主页: 33的博客❣ ▶️文章专栏分类:JavaEE◀️ &#x1f69a;我的代码仓库: 33的代码仓库&#x1f69a; &#x1faf5;&#x1faf5;&#x1faf5;关注我带你了解更多进阶知识 目录 1.前言2.响应2.1返回静态界面2.2返回数据2.3返回HTML代码 3.综合练习3.1计算器3.2用户登…

Python 技能提升(二)

理想的类结构 Property装饰器 # 传统写法 class Square1:def __init__(self):self.__side Nonedef get_side(self):return self.__sidedef set_side(self, side):assert side > 0, 边长不能为负数&#xff01;self.__side sidedef del_side(self):# del self.__sideself.…

点到线段的最短矩离 及垂足的计算

过P做MN的垂线&#xff0c;垂足为Q&#xff0c;若Q在线段MN以内(包括与点M点N重合)&#xff0c;则最短距离为垂线段长度&#xff0c;若垂足在MN以外&#xff0c;则最短距离为PM&#xff0c;PN中的较小者。&#xff08;若P与MN共线&#xff0c;垂线长度为零&#xff0c;同样适用…

使用 MobileNet和ImageHash做图片相似度匹配(以图搜图)

很多应用中有以图搜图的应用&#xff0c;那么我们应该如何实现呢&#xff1f; 传统的文本搜索主要是关键字匹配&#xff0c;而目前图片和音乐的搜索却使用使用特征向量的方式。 向量就是使用一组数从多个维度描述特征&#xff0c;虽然每个维度的含义我们可能无法得知&#xff…

彻底卸载Windows Defender

概述 卸载Windows Defender的方法有很多&#xff0c;如修改注册表、组策略&#xff0c;执行脚本等等&#xff0c;这些方法操作过于繁琐和复杂&#xff0c;不适合小白&#xff0c;今天带来一款强大的卸载工具&#xff0c;只需要以管理员身份运行该软件即可&#xff0c;不用其他操…

css特殊效果和页面布局

特殊效果 圆角边框&#xff1a;div{border-radius: 20px 10px 50px 30px;} 四个属性值按顺时针排列&#xff0c;左上的1/4圆半径为20px&#xff0c;右上10&#xff0c;右下50&#xff0c;左下30。 div{border-radius: 20px;} 四角都为20px。 div{border-radius: 20px 10…

系统架构设计师【第12章】: 信息系统架构设计理论与实践 (核心总结)

文章目录 12.1 信息系统架构基本概念及发展12.1.1 信息系统架构的概述12.1.2 信息系统架构的发展12.1.3 信息系统架构的定义 12.2 信息系统架构12.2.1 架构风格12.2.2 信息系统架构分类12.2.3 信息系统架构的一般原理12.2.4 信息系统常用4种架构模型12.2.5 企业信息系…

finebi或者finereport发邮件

我们二次开发中&#xff0c;如果想利用产品自带的发邮件的功能&#xff0c;来发送自己的邮件内容。 首先 决策系统中邮件相关信息要配置好之后&#xff1a; 这里配好了发件人&#xff0c;以及默认发件人后&#xff0c; private void sendEmail(String content,String subject)…

Nvidia Jetson/Orin +FPGA+AI大算力边缘计算盒子:潍柴雷沃智慧农业无人驾驶

潍柴雷沃智慧农业科技股份有限公司&#xff0c;是潍柴集团重要的战略业务单元&#xff0c;旗下收获机械、拖拉机等业务连续多年保持行业领先&#xff0c;是国内少数可以为现代农业提供全程机械化整体解决方案的品牌之一。潍柴集团完成对潍柴雷沃智慧农业战略重组后&#xff0c;…

ROS无人机追踪小车项目开发实战 | 第四届中国智能汽车创新大会圆满结束

2024年5月26日&#xff0c;阿木实验室在深圳第四届中国智能汽车创新大会上&#xff0c;开展的《Prometheus开源平台-ROS无人机追踪小车项目开发实战课》圆满结束。 该实战课从初学者的角度出发&#xff0c;通过实践性讲解和开发&#xff0c;使开发者们系统地学习了硬件系统架构…

Geotools--生成等值线

好久没用geotools去写东西了&#xff0c;因为近几年一直在接触所谓数字孪生和可视化相关项目&#xff0c;个人的重心也往前端可视化去倾斜&#xff0c;在后端的开发上到变得停滞下来。 这次用的是geotools 28.4版本&#xff0c;生成等值线的方法在 <dependency><group…

进程与线程(四)

进程与线程&#xff08;四&#xff09; 基于System V IPC对象的进程间通信机制SystemV IPC引入查看Linux系统中IPC工具的方式查看所有IPC工具命令&#xff1a;ipcs 查看指定的IPC工具key值获取方法&#xff1a;ftok()函数 消息队列消息队列的特征&#xff1a;消息队列的操作打开…

数学建模 —— 插值与拟合(1)

一、matlab画图 1.1 plot&#xff08;二维图形&#xff09; plot(x) —— 缺省自变量绘图格式 plot(x,y) —— 基本格式&#xff0c;以y(x)的函数关系作出直角坐标图&#xff0c;如果y为nm的矩阵&#xff0c;则以x为自变量&#xff0c;作出m条曲线 plot(x1,y1,x2,y2,…,xn,…