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

leetcode面试题:交换和(三种方法实现)

交换和:

给定两个整数数组,请交换一对数值(每个数组中取一个数值),使得两个数组所有元素的和相等。

返回一个数组,第一个元素是第一个数组中要交换的元素,第二个元素是第二个数组中要交换的元素。若有多个答案,返回任意一个均可。若无满足条件的数值,返回空数组。

示例:

输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]
输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
输出: []

解题思路:

1.首先,先对题目进行理解,交换两个数,使得两个数组的和相等,那么就需要分别把两个数组的和计算出来,如果sum1和sum2的差值为偶数,才有可能可以找到能够交换的数。如果差值为奇数,直接返回空数组。

2.sum1和sum2的差值为偶数时,diff=(sum1-sum2)/2,存在:

sum1-array1[i]+array2[j] = sum2-array2[j]+array1[i]

array1[i]+diff=array2[j]

此时可以满足交换之后,sum1=sum2

方法一:排序+二分查找法

Code:

class Solution {
public:vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {sort(array2.begin(), array2.end());int sum1 = 0, sum2 = 0, m = array1.size(), n = array2.size();for (int & num : array1) sum1 += num;//计算sum1for (int & num : array2) sum2 += num;//计算sum2//如果差值为奇数,不会存在两个数符合题意if ((sum2 -sum1) % 2) return {}; // 两个数组的差值必须是偶数int diff = (sum2 - sum1) / 2;	// 需满足 y = x + diff;for (int i = 0;i < m; i++) {int target = array1[i] + diff;int left = 0, right = n - 1, mid;//对数组2进行二分查找法while (left <= right) {mid = (right + left) >> 1;//找到目标元素if (array2[mid] == target) {return {array1[i], array2[mid]};}else if (array2[mid] > target) right = mid - 1;else left = mid + 1;}}return {};	// 没有找到符合题意的两个数}
};

方法二:排序+双指针

class Solution {
public:vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {sort(array1.begin(), array1.end());     // 对array1排序sort(array2.begin(), array2.end());     // 对array2排序int sum1 = 0, sum2 = 0;for (int num : array1) sum1 += num;   // 数组1求和for (int num : array2) sum2 += num;   // 数组2求和if ((sum1 -sum2) % 2) return {}; // 两个数组的差值必须是偶数int diff = (sum1 - sum2) / 2;   // 需满足 x - y = diffint i = 0, j = 0, m = array1.size(), n = array2.size();while (i < m && j < n) {    // 双指针寻找满足条件的值if (array1[i] - array2[j] < diff) i++;  else if (array1[i] - array2[j] > diff) j++;else return {array1[i], array2[j]};     // 找到符合题意得值,直接返回两个元素即可}return {}; //  未找到符合题意的两个数}
};

方法三:哈希表(因为哈希表可以直接查找,所以就不需要排序了)

class Solution {
public:vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {int sum1 = 0, sum2 = 0;for (int num : array1) sum1 += num;//数组1求和for (int num : array2) sum2 += num;//数组2求和if ((sum1 -sum2) % 2) return {};  // 两个数组的差值必须是偶数//将array2的所有元素放入哈希表中unordered_set<int> arr(array2.begin(), array2.end()); int diff = (sum1 - sum2) / 2; //遍历array1for (int x : array1) {//假定当前array1中要交换的是x,那么在哈希表中找y,如果存在,那就可以交换int y = x - diff; if (setArr2.count(y)) return {x, y};}return {};}
};

相关文章:

leetcode面试题:交换和(三种方法实现)

交换和&#xff1a; 给定两个整数数组&#xff0c;请交换一对数值&#xff08;每个数组中取一个数值&#xff09;&#xff0c;使得两个数组所有元素的和相等。 返回一个数组&#xff0c;第一个元素是第一个数组中要交换的元素&#xff0c;第二个元素是第二个数组中要交换的元…...

前端可视化界面开发技术:实战与优化

引言 在当今的互联网时代&#xff0c;数据可视化已经成为信息展示和交互的重要方式。特别是在前端开发领域&#xff0c;可视化界面的应用越来越广泛&#xff0c;涉及到数据监控、分析和决策等多种场景。本文将深入探讨前端可视化界面开发的关键技术&#xff0c;通过实例解析提…...

Python实现机器学习(下)— 数据预处理、模型训练和模型评估

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。本门课程将介绍人工智能相关概念&#xff0c;重点讲解机器学习原理机器基本算法&#xff08;监督学习及非监督学习&#xff09;。使用python&#xff0c;结合sklearn、Pycharm进行编程&#xff0c;介绍iris&#xff08;鸢尾…...

树结构处理,list和tree互转

1、实体类 package com.iot.common.test.entity;import lombok.Data;import java.util.List;/*** description:* author:zilong* date:2023/9/8*/ Data public class Node {//idprivate String id;//父节点idprivate String pId;//名称private String name;//编码private Stri…...

可视化大屏设计模板 | 主题皮肤(报表UI设计)

下载使用可视化大屏设计模板&#xff0c;减少重复性操作&#xff0c;提高报表制作效率的同时也确保了报表风格一致&#xff0c;凸显关键数据信息。 软件&#xff1a;奥威BI系统&#xff0c;又称奥威BI数据可视化工具 所属功能板块&#xff1a;主题皮肤上传下载&#xff08;数…...

Spring Boot + Vue的网上商城之客服系统实现

Spring Boot Vue的网上商城之客服系统实现 在网上商城中&#xff0c;客服系统是非常重要的一部分&#xff0c;它能够为用户提供及时的咨询和解答问题的服务。本文将介绍如何使用Spring Boot和Vue.js构建一个简单的网上商城客服系统。 思路 在本教程中&#xff0c;我们学习了…...

RabbitMQ: return机制

1. Return机制 Confirm只能保证消息到达exchange&#xff0c;无法保证消息可以被exchange分发到指定queue。 而且exchange是不能持久化消息的&#xff0c;queue是可以持久化消息。 采用Return机制来监听消息是否从exchange送到了指定的queue中 2.Java的实现方式 1.导入依赖 &l…...

记录一些奇怪的报错

错误&#xff1a;AttributeError: module distutils has no attribute version 解决方案&#xff1a; 第一步&#xff1a;pip uninstall setuptools 第二步&#xff1a;conda install setuptools58.0.4 错误&#xff1a;ModuleNotFoundError: No module named _distutils_hac…...

Ubuntu 安装redis数据库,并设置开机自启动

1、下载安装包 wget http://download.redis.io/releases/redis-7.0.9.tar.gz 2、解压 tar -zxvf redis-7.0.9.tar.gz 3、复制到解压缩的包移动到/usr/local/ sudo mv ./redis-7.0.9 /usr/local/ 4、编译 cd /usr/local/redis-7.0.9 sudo make 5、测试: 时间会比较长&#xff0…...

基于开源模型搭建实时人脸识别系统(五):人脸跟踪

继续填坑&#xff0c;之前已经讲了人脸检测&#xff0c;人脸识别实战之基于开源模型搭建实时人脸识别系统&#xff08;二&#xff09;&#xff1a;人脸检测概览与模型选型_开源人脸识别模型_CodingInCV的博客-CSDN博客&#xff0c;人脸检测是定位出画面中人脸的位置&#xff0c…...

VUE | 配置环境变量

本篇目录 1. 创建开发环境配置文件2. 创建正式环境配置文件3. 在代码中访问环境变量4. 加载环境变量 在 Vue 项目中是使用 .env 文件来定义和使用不同的环境变量&#xff0c;这些文件在 Vue 项目根目录下创建。推荐有几种环境就创建几个 .env 文件&#xff0c;下面就开发环境和…...

Dynamic-TP入门初探

背景 在使用线程池的过程中&#xff0c;会出现一些痛点&#xff1a; 代码中创建了一个线程池&#xff0c;但是不知道那几个核心参数设置多少比较合适。凭经验设置参数值&#xff0c;上线后发现需要调整&#xff0c;改代码重新发布服务&#xff0c;非常麻烦。线程池相对开发人…...

Git的基本操作:远程操作

7 Git的远程操作 远程操作主要是指&#xff0c;在不同的仓库之间进行提交和代码更改。是一个明显的对等的分布式系统。其中本地个仓库与远程仓库&#xff0c;不同的远程仓库之间都可以建立这种关系。这种关系之间的操作主要有pull和push。 远程仓库 创建SSH key远程仓库和本…...

【IOC,AOP】spring的基础概念

IOC 控制反转 对象的创建控制权转交给外部实体&#xff0c;就是控制反转。外部实体便是IOC容器。其实就是以前创建java对象都是我们new一下&#xff0c;现在我们可以把这个new交给IOC容器来做&#xff0c;new出来的对象也会交由IOC容器来管理。这个new出来的对象则称为Bean。 …...

安全实战 | 怎么用零信任防范弱密码?

防范弱密码&#xff0c;不仅需要提升安全性&#xff0c;更需要提升用户体验。 比如在登录各类业务系统时&#xff0c;我们希望员工登录不同系统不再频繁切换账号密码&#xff0c;不再需要3-5个月更换一次密码&#xff0c;也不再需要频繁的输入、记录、找回密码。 员工所有的办…...

1-4 AUTOSAR方法论

总目录——AUTOSAR入门详解AUTOSAR入门详解目录汇总&#xff1a;待续中。。。https://xianfan.blog.csdn.net/article/details/132818463 目录 一、前言 二、方法论 三、单个ECU开发流程 一、前言 汽车生产供应链上有以下角色&#xff1a;OEM、TIER1、TIER2&#xff0c;其主…...

MFC C++ 数据结构及相互转化 CString char * char[] byte PCSTR DWORE unsigned

CString&#xff1a; char * char [] BYTE BYTE [] unsigned char DWORD CHAR&#xff1a;单字节字符8bit WCHAR为Unicode字符:typedef unsigned short wchar_t TCHAR : 如果当前编译方式为ANSI(默认)方式&#xff0c;TCHAR等价于CHAR&#xff0c;如果为Unicode方式&#xff0c…...

多版本CUDA安装切换

系统中默认的安装CUDA为12.0&#xff0c;现在需要在个人用户下安装CUDA11.7。 CUDA 下载 CUDA官网下载 安装 Log file not open.Segmentation fault (core dumped)错误 将/tmp/cuda-installer.log删除即可。重新安装&#xff0c;去掉驱动的安装&#xff0c;设置Toolkit的安装…...

sqlserver union和union all 的区别

1.首先在数据库编辑1-40数字&#xff1b; 2.查询Num<30的数据&#xff0c;查询Num>20 and Num<40的数据&#xff0c;使用union all合并&#xff1b; 发现30-20的数字重复了&#xff0c;可见union all 不去重&#xff1b; 3.查询Num<30的数据&#xff0c;查询Num…...

Matlab 如何计算正弦信号的幅值和初始相角

Matlab 如何计算正弦信号的幅值和初始相角 1、概述 如果已知一个正弦信号的幅值&#xff0c;在FFT后频域上该信号谱线的幅值与设置值不同&#xff0c;而是大了许多&#xff1b;如果不知道某一正弦信号的幅値&#xff0c;又如何通FFT后在頻域上求出该正弦信号的幅值呢? 2、…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...