首页 > 其他分享 >167. 两数之和 II - 输入有序数组

167. 两数之和 II - 输入有序数组

时间:2023-07-08 11:00:23浏览次数:46  
标签:index1 target int II numbers 数组 index2 167 两数

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列  ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1)
当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n)
当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n)
以此类推

题中要求的 常数级别的额外空间 就是O(1)
 
示例 1:

输入:numbers = [2,7,11,15], target = 9
输出:[1,2]
解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:

输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3:

输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int* flag = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;
    for (int i = 0; i < numbersSize; ++i) {
    int low = i + 1, high = numbersSize - 1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] == target - numbers[i]) {
            flag[0] = i + 1, flag[1] = mid + 1;
            return flag;} 
        else if (numbers[mid] > target - numbers[i])
            high = mid - 1;
        else
            low = mid + 1;
    }
}
flag[0] = -1, flag[1] = -1;
return flag;
}

使用二分法,先把首位数字位置固定,从后往前进行二分法,由于数组是顺序排列,所以可以根据大小对二分的范围进行缩小,最后找到需要的值

标签:index1,target,int,II,numbers,数组,index2,167,两数
From: https://www.cnblogs.com/noobwei/p/17536893.html

相关文章

  • STM32IO口模拟IIC时序
    正点原子IIC讲解:https://www.bilibili.com/video/BV1o8411n7o9/?spm_id_from=333.337.search-card.all.click&vd_source=e35b16eeaf19ae2b23ff9587a735ee20一、IIC总线1.物理层(1)支持多设备,一个IIC通讯总线中可以连接多个IIC设备,支持多个通讯主机及多个通讯从机;(2)两条线:双......
  • 1644 题「二叉树的最近公共祖先 II
    对于这道题来说,p和q不一定存在于树中,所以你不能遇到一个目标值就直接返回,而应该对二叉树进行完全搜索(遍历每一个节点),如果发现p或q不存在于树中,那么是不存在LCA的。  ......
  • 51. N 皇后&52. N 皇后 II
    按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n 皇后问题研究的是如何将n 个皇后放置在n×n的棋盘上,并且使皇后彼此之间不能相互攻击。给你一个整数n,返回所有不同的 n 皇后问题的解决方案。每一种解法包含一个不同的 n皇后问题的棋......
  • 错误:rpmdb: BDB0113 Thread/process 8709/139671674841152 failed
    rpm库报错错误:rpmdb:BDB0113Thread/process8709/139671674841152failed:BDB1507ThreaddiedinBerkeleyDBlibrary错误:db5错误(-30973)来自dbenv->failchk:BDB0087DB_RUNRECOVERY:Fatalerror,rundatabaserecovery错误:无法使用db5- (-30973)打开Packages......
  • 【暑假题目】20030703 两数相加
    两数相加题目请使用C++计算出2^2023与3^2023的和题目分析首先通过题目,我们将所求的两个加数看为a,b,我们可以关注到两个点:1.首先要解决的是两个加数的求法,这里分别有两种求法:①通过for循环求得a,b两个加数。②通过指数函数pow函数得到a,b两个加数。在可以调用函数的情况下......
  • 4.3 Recurrent Neural Network (RNN) II
    1.RNN怎么学习1.1LossFunction  如果要做learning的话,你要定义一个costfunction来evaluate你的model是好还是不好,选一个parameter要让你的loss最小.那在RecurrentNeuralNetwork里面,你会怎么定义这个loss呢,下面我们先不写算式,先直接举个例子.  如下图所示,这是一......
  • 软件IIC SDA输入输出
    SDA输入输出模式改变方式一  SCL线可以配置推挽输出,开漏输出(有上拉电压存在)都可,因为不用兼具输入扫描功能;SDA线必须配置开漏输出,电路上要外加上拉电阻,因为要兼具输入扫描功能, 方式二 对应的gpio口配置代码的改变#defineSCCB_SDA_IN(){GPIOG->CRH&=0X......
  • 光学成像系统 Part III - BRDF测试数据使用 (二)
    一、BRDF实验数据使用方法1.数据集-下载I.数据集格式(AnisotropicBRDFDataFileFormat)解压后的数据集以.dat尾缀结束,文件包括了64Bytes的文件头,用来表示文件中数据的维度,存储格式等信息,在表头之后的便是对应的数据值,具体如下所示:\[3(RGB)\timesdim[0]\timesdim......
  • 代码随想录算法训练营第二十四天| 491.递增子序列 46.全排列 47.全排列 II
     491.递增子序列 此题的难点:1,前提需要保留原有顺序2,保证递增3,保证去重注意:去重一定要有set的同时保证有顺序代码:1voidfindSubsequences_trackBack(vector<int>&nums,intstartIndex,vector<int>&path,vector<vector<int>>&result)2{3if(path.size(......
  • 123. 买卖股票的最佳时机 III
    1.题目读题  考查点 2.解法思路 有两种解法动态规划双指针代码逻辑 具体实现 动态规划思路动态规划的思路是这样的:我们可以把问题分解成多个子问题,每个子问题都是在某一天结束时,完成了多少次交易,手上是否持有股票,以及此时的最大利润是多少。我们......