剑指Offer 两数之和 - 输入有序数组

ops/2024/12/24 21:57:48/

题目链接

剑指Offer 两数之和 - 输入有序数组

思路

思路一 暴力

两层循环,外层循环固定一个值(value),内层循环寻找是否存在target-value,若存在就返回

public int[] twoSum(int[] numbers,int target){int[] res = new int[2];for(int i=0;i<numbers.length;i++){int value = numbers[i];for(int j=i+1;j<numbers.length;j++){if(numbers[j] == target - value){res[0] = i;res[1] = j;return res;}}}return res;
}

时间复杂度:O( N 2 N^2 N2)
空间复杂度:O(N)

思路二 循环+二分

即外层循环固定一个值,内层用二分查找在数组中查找target-value

int binarySearch(int[] nums,int start,int target){int i = start,j = nums.length-1;while (i<=j){int mid = (i+j)/2;if(nums[mid] == target)return mid;else if(nums[mid] > target){j--;}elsei++;}return -1;
}
public int[] twoSum(int[] nums,int target){int[] res = new int[2];for(int i=0;i<nums.length;i++){int value = nums[i];int index = binarySearch(nums,i+1,target-value);if(index!=-1){return new int[]{i,index};}}return res;
}

时间复杂度:O(Nlogn)
空间复杂度:O(N)

思路三 双指针

这个思路我没有想出来

双指针的本质是缩小搜索空间

别人的想法:别人的想法
题目中的解空间是 i , j ∣ 0 < = i < n , 0 < = j < = n {i,j}|0<=i<n,0<=j<=n i,j∣0<=i<n,0<=j<=n
搜索空间如下是白色的倒三角部分,因为题目要求i<j

在这里插入图片描述

初始状态,i=0,j=n
在这里插入图片描述

对于nums[0]+nums[7]与target的大小关系,要么大于,要么小于,要么等于,等于直接就返回就行。下面来分析小于的情况
由于nums[0]+nums[7]<target,我们需要找更大的两个数字,但nums[7]已经是最大的了,所以只能对i进行操作,那么是+1还是-1?
考虑+1的可能性
nums[0] + nums[7]<target
那么nums[0]+nums[7]<nums[1]+nums[7]<=target
因为是升序的
考虑-1的可能性
nums[i] + nums[j] < target
那么nums[i-1]+nums[j]<nums[i]+nums[j]<target
所以在和小于target的情况下,只可能对i+1

考虑大于的时候
nums[0]+nums[7]>target
我们需要找小于的情况,你不可能将nums[0]换成nums[1],因为nums[1]+nums[7]>target
所以只可能更改nums[7],让nums[7]换成nums[6]

所以代码如下

class Solution {public int[] twoSum(int[] numbers, int target) {int[] res = new int[2];int i = 0,j=numbers.length-1;while (i<j){int sum = numbers[i] + numbers[j];if(sum==target){res = new int[]{i+1,j+1};return res;}else if(sum>target){j--;}else if(sum<target){i++;}}return res;}
}

http://www.ppmy.cn/ops/144676.html

相关文章

【CCNA网络】Multimode Fiber和Single Mode Fiber是什么?(MMF)(多模光纤)(SMF)(单模光纤)

考点浓缩&#xff1a; 多模光纤&#xff08;MMF&#xff09;和单模光纤&#xff08;SMF&#xff09;是两种常见的光纤类型。单模光纤具有较小的纤芯&#xff08;约8-10μm&#xff09;&#xff0c;适用于长距离、高带宽的传输&#xff08;如城际连接&#xff09;。多模光纤具有…

Django 应用安装脚本 – 如何将应用添加到 INSTALLED_APPS 设置中 原创

什么是 INSTALLED_APPS&#xff1f; INSTALLED_APPS 是 Django 项目中的一个设置&#xff0c;它用于列出项目中所使用的所有应用程序。每当你创建或安装一个新的应用程序时&#xff0c;你需要将其添加到 INSTALLED_APPS 中&#xff0c;以便 Django 项目可以识别并使用该应用程序…

自己搭建专属AI:Llama大模型私有化部署

前言 AI新时代&#xff0c;提高了生产力且能帮助用户快速解答问题&#xff0c;现在用的比较多的是Openai、Claude&#xff0c;为了保证个人隐私数据&#xff0c;所以尝试本地&#xff08;Mac M3&#xff09;搭建Llama模型进行沟通。 Gpt4all 安装比较简单&#xff0c;根据 G…

深圳龙岗戴尔dell r730xd服务器故障维修

深圳龙岗一台DELL POWEREDGE R730XD服务器系统故障问题处理&#xff1a; 1&#xff1a;客户工厂年底产线整改&#xff0c;时不时的会意外断电&#xff0c;导致服务器也频繁停机&#xff0c; 2&#xff1a;多次异常停机后导致服务器开机后windows server系统无法正常启动了&…

Facebook的去中心化探索:社交平台的新型发展趋势

随着数字化进程的加速&#xff0c;社交平台的架构正在经历一场深刻的变革。从最初的集中的社交网络到如今去中心化的构想&#xff0c;社交平台正在朝着更加透明、开放和用户主导的方向发展。作为全球最大的社交平台之一&#xff0c;Facebook&#xff08;现Meta&#xff09;也在…

每天40分玩转Django:Django文件上传

Django文件上传 一、今日学习内容概述 学习模块重要程度主要内容基础文件上传⭐⭐⭐⭐⭐文件字段、基本配置自定义存储⭐⭐⭐⭐⭐存储后端、云存储集成文件处理⭐⭐⭐⭐图片处理、文件验证异步上传⭐⭐⭐⭐AJAX上传、进度显示 二、模型和表单设计 # models.py from django.…

Oracle下载安装(保姆级教学)

方法1 1. 官网下载安装包 对于 Oracle 软件的下载&#xff0c;建议通过官网免费下载&#xff0c;安全且有保证。 下载地址&#xff1a; https://www.oracle.com/database/technologies/oracle19c-windows-downloads.html 通过下载页面可以选择安装压缩包&#xff08; WIND…

Linux学习——9_Ubuntu Linux操作系统

Ubuntu Linux操作系统 Ubuntu简介 Ubuntu Linux是由南非人马克沙特尔沃思(Mark Shuttleworth)创办的基于Debian Linux的操作系统&#xff0c;于2004年10月公布 Ubuntu是一个以桌面应用为主的Linux发行版操作系统 Ubuntu拥有庞大的社区力量&#xff0c;用户可以方便地从社区…