首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在一个数组中查找两个数的最好方法,它们的和是一个特定的数

在一个数组中查找两个数的和为特定值的最佳方法是使用双指针法。该方法通过设置两个指针,一个指向数组的起始位置,另一个指向数组的末尾位置,然后根据指针所指元素的和与目标值的关系来移动指针,直到找到目标值或者遍历完整个数组。

以下是双指针法的实现步骤:

  1. 首先将数组进行排序,这样可以更方便地移动指针。
  2. 设置两个指针,一个指向数组的起始位置(一般为0),称为左指针;另一个指向数组的末尾位置(一般为数组长度减1),称为右指针。
  3. 分别获取左指针和右指针所指的元素,并计算它们的和。
  4. 如果和等于目标值,则返回这两个数。
  5. 如果和小于目标值,则将左指针向右移动一位,即左指针加1。
  6. 如果和大于目标值,则将右指针向左移动一位,即右指针减1。
  7. 重复步骤3到步骤6,直到找到目标值或者左指针大于等于右指针。

双指针法的时间复杂度为O(nlogn),其中n是数组的长度,这是因为需要对数组进行排序。排序的时间复杂度为O(nlogn)。另外,双指针法的空间复杂度为O(1),即不需要额外的空间。

以下是一个示例的代码实现(使用Python语言):

代码语言:txt
复制
def twoSum(nums, target):
    nums.sort()
    left = 0
    right = len(nums) - 1
    
    while left < right:
        sum = nums[left] + nums[right]
        if sum == target:
            return [nums[left], nums[right]]
        elif sum < target:
            left += 1
        else:
            right -= 1
    
    return None

在云计算领域中,可以使用腾讯云的云服务器(ECS)来运行上述代码。云服务器是一种提供计算能力的基础设施服务,可以按需购买、弹性扩展和灵活管理。您可以通过以下链接了解更多关于腾讯云云服务器的信息:https://cloud.tencent.com/product/cvm

请注意,以上答案是在没有提及云计算品牌商的情况下给出的。如果需要具体了解某个品牌商的相关产品和服务,建议直接访问品牌商的官方网站或咨询相关技术支持人员。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

输入一个已经按升序排序过数组一个数字,在数组查找个数,使得它们正好输入个数

题目: 输入一个已经按升序排序过数组一个数字, 在数组查找个数,使得它们正好输入个数字。 要求时间复杂度O(n)。如果有多对数字等于输入数字,输出任意一对即可。...思路: 1 第一种思路,可以把数字存在数组里,比如数组中最大值15,那么就开一个长度未15数组1 存在a[1]里 15存在a[15]里;这样用15-a[1]判断里面是否有值就可以了。...2 因为个数,时间复杂度O(n),还是排过顺序数组,那么可以从头从尾同时找;从尾开始tail下标大于sum,则tail左移;如果tailhead相加小于sum,则tail右移;指导头尾个数相加等于求和...;或者tail大于head为止; 代码如下: ''' 题目:输入一个已经按升序排序过数组一个数字, 在数组查找个数,使得它们正好输入个数字。...个数找K个最小

2.2K10
  • Linux统计一个文件特定字符个数方法

    统计一个文件某个字符串个数,其实就是在在一块沙地里面找石头,有的人看到石头以后,在上面做个标记(grep),然后记住自己做了多少个标记;有的人看到石头以后,把它挖了(tr),最后统计自己挖了多少石头...[root@bzhou test]# awk -v RS='haha' 'END {print --NR}' file -v 去设定一个变量值,RS记录分隔符,默认新行(\n),就是说awk按照一行一行读数据...,但是现在RS为’haha’后,就按’haha’读数据了,NR为已读记录,n个记录被n-1个分隔符分开,所以就是–NR了。...这里就匹配这个文件‘h’个数。...test]# tr -cd 'h' <file | wc -c 8 [root@bzhou test]# grep -o 'h' file | wc -l 8 -d可以删除某个字符,如果只有-d就会输出删除特定字符后字符串

    5.7K40

    关于一个数组个数等于给定数问题

    今天我遇到这样一个问题,问题描述如下:         给出一个数组,再给定一个数target,如果数组中有个数等于target,那么返回这个数索引,如果说有多对数都符合条件则返回第一对,返回结果用一个长度为...,但是新问题会出现,如果个数相同的话,那么删除元素方法不能够解决,基于上述无法解决问题,我们想到了map,mapkey保存数组,而value则存着个数索引,思路当遍历到元素...n时判断,target-n是否map,如果在则返回索引,这是还是会出现上述个问题,首先如果有多个数重复时候,那么map一个数value值存放,这些相同最后一个索引,所以我们判断是否存在这样一对时候再加上条件...,其实还可以扩展到三个数,问题描述可以是这样,从一个数组找出三个数索引,让他们等于0,如果用穷举法的话,那么时间复杂度将达到o(n*n*n),但是如果运用上面的思路的话,遍历数组,选取一个数作为...3个数一个数n,然后从剩余找出个数等于-n个数,那么这样的话,时间复杂度会减少到o(n*n),并且如果再仔细斟酌,那么第一个遍历过都不会被算在内,那么程序将会更加快,这里只提供思路

    75920

    经典算法题 -- 寻找一个数组不重复个数

    因为个相同数字异或等于 0,一个数 0 异或还是它本身,利用这一特性,将数组中所有数字异或,最终出现所有数字异或结果为 0,只有出现一次数字与 0 异或返回了它本身,于是我们找到了这个只出现了一次数字...但题目中出现一次数字个不相同,所以如果我们仍然将所有数字异或,最终将会得到这个不相同数字异或结果,我们是否有办法异或结果中将个数字还原为原来数字或转化为寻找数组只出现一次一个数字呢...办法有的,既然个数不同,那么最终异或结果一定不为 0,而这个结果数字,为 1 位表示个出现一次,这位不同。...假设异或结果数字,第 n 位为 1,则说明个只出现一次数字一个第 n 位为 1,一个第 n 位为 0,我们可以将原数组划分为个数组,分别是所有第 n 位为 0 数组数组所有第 n...位为 1 数组数组,这样既可以保证所有相同都被放入同一个数组,也可以保证个只出现了一次数分别被放入个不同数组,于是,最终我们将问题转化为找到分别在个数组找到每个数组只出现一次一个数

    1.1K40

    2023-07-27:最长可整合子数组长度, 数组数字排序之后,相邻差值1, 这种数组就叫可整合数组。 给定一个数

    2023-07-27:最长可整合子数组长度, 数组数字排序之后,相邻差值1, 这种数组就叫可整合数组。 给定一个数组,求最长可整合子数组长度。...7.开始从start+1位置向后遍历数组,每次迭代终止条件end < len(arr)。 8.如果arr[end]set已经存在,表示遇到了重复元素,跳出循环。...9.返回最长可整合子数组长度ans。 算法maxLen时间复杂度空间复杂度分别为: 时间复杂度: • 最坏情况下,需要遍历输入数组每个元素,所以时间复杂度为O(n),其中n输入数组长度。...空间复杂度: • 使用了一个set容器来存储元素,所以空间复杂度为O(n),其中n输入数组长度。...• 因此,整个算法时间复杂度为O(n^2 log n),其中n输入数组长度。 空间复杂度: • 使用了一个辅助数组help存储子数组拷贝,所以空间复杂度为O(n),其中n输入数组长度。

    15730

    如何高效判断一个数组里是否含特定元素判断一个数组里是否含有特定元素四种方法时间复杂度测试小结

    如何高效判断一个数组里是否含特定元素?...这是我们实际开发中经常遇到一个问题,也是Stack Overflow上热门问题,解决这个问题有很多不同方法,但是不同方法时间复杂度却差别很大,所以本文会列举常用几种方法,并且对比每个方法耗时...判断一个数组里是否含有特定元素四种方法 使用list //Using List public static boolean useList(String[] arr, String targetVal...小结 我们发现当数组无序时候,我们如果要判断一个数组是否含有一个元素,应该使用直接循环查找,这样效率最高,如果数组有序情况下,我们应该使用二分查找,此外,如果hashset或hashmap...查找一个元素直接调用collection库就可以了。

    1.2K20

    排序数组查找元素一个最后一个位置

    前言: 这是一道给很经典二分查找题目,并且该二分查找算法不同于简单二分,二分查找进阶版本。 一、题目描述 34....排序数组查找元素一个最后一个位置 给你一个按照非递减顺序排列整数数组 nums,一个目标值 target。请你找出给定目标值在数组开始位置结束位置。...如果数组不存在目标值 target,返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 算法解决此问题。...其实这部分大同小异,只要弄懂其中一个,另一个就迎刃而解! 我们首先来讲第一部分——求该元素左端点。 第一步将这些数据分为个部分:小于元素大于等于该元素这个部分。...因为左端点将数据分为小于大于等于,所以right = mid,如果这里采用第二种求中点方法,就会造成死循环,right值一直都没有变化! 上面就是讲解左端点解法,右端点也是大同小异。

    10010

    排序数组查找元素一个最后一个位置

    排序数组查找元素一个最后一个位置 给定一个按照升序排列整数数组 nums,一个目标值 target。找出给定目标值在数组开始位置结束位置。...接下来,去寻找左边界,右边界了。 采用二分法来去寻找左右边界,为了让代码清晰,我分别写个二分来寻找左边界右边界。...刚刚接触二分搜索同学不建议上来就像如果用一个二分来查找左右边界,很容易把自己绕进去,建议扎扎实实个二分分别找左边界右边界 寻找右边界 先来寻找右边界,至于二分查找,如果看过704.二分查找就会知道...nums 数组中二分查找得到第一个大于等于 target下标(左边界)与第一个大于target下标(右边界); # 2、如果左边界<= 右边界,则返回 [左边界, 右边界]。...nums 数组中二分查找得到第一个大于等于 target下标leftBorder; # 2、 nums 数组中二分查找得到第一个大于等于 target+1下标, 减1则得到rightBorder;

    4.7K20

    LeetCode-34-排序数组查找元素一个最后一个位置

    # LeetCode-34-排序数组查找元素一个最后一个位置 给定一个按照升序排列整数数组 nums,一个目标值 target。找出给定目标值在数组开始位置结束位置。...你算法时间复杂度必须 O(log n) 级别。 如果数组不存在目标值,返回 [-1, -1]。...1、双指针暴力法(low): 特例判断: 当数组为空或数组长度为0时,直接返回[-1,1] 当数组长度为1时,判断第一个数字是否等于target,等于则返回[0,0],否则返回[-1,-1] 初始化头尾指针...,说明只有一个target,返回当前位置[start,start]或[end,end] 反之,返回头尾指针区间[start,end] 方法2、二分查找(fast): 通过判断mid位置数值,决定左右边界移动...,-1] 方法3、递归分治(low): 通过二分查找切分数组寻找左右子数组target位置,迭代到只有一个,判断是否目标值,返回一个都是当前index数组,然后进行合并即可 方法4、二次二分找左右边界

    2.2K20

    Leetcode No.34 排序数组查找元素一个最后一个位置

    一、题目描述 给定一个按照升序排列整数数组 nums,一个目标值 target。找出给定目标值在数组开始位置结束位置。 如果数组不存在目标值 target,返回 [-1, -1]。...3: 输入:nums = [], target = 0 输出:[-1,-1] 提示: 0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 一个非递减数组...-109 <= target <= 109 二、解题思路 使用二分法查找一个位置,初始化个变量low=0,hight=nums.length-1 1、当low>high时,表示没有找到,返回-1...nums[mid]时,说明目标值左侧,往左侧递归查找,否则往右侧递归查找 查找最后一个位置同理,唯一不同第4、5步 4、假如nums[mid]等于target且nums[mid]比相邻右侧元素小...二分查找时间复杂度为 O(logn),一共会执行次,因此总时间复杂度为O(logn)。 空间复杂度:O(1) 。只需要常数空间存放若干变量。

    1.9K10

    leetcode-34-排序数组查找元素一个最后一个位置

    题目描述: 给定一个按照升序排列整数数组 nums,一个目标值 target。找出给定目标值在数组开始位置结束位置。 你算法时间复杂度必须 O(log n) 级别。...: vector searchRange(vector& nums, int target)  说明: 1、这道题给定一个vector一个target,vector中装着升序一个数组...,比如[5,7,7,8,8,10], 要求找到target比如8,vector起始位置结束位置。...如果在vector找不到target,那么返回[-1,-1]。 2、这道题又是一道二分法题目,不过二分法一个变种。...按照二分法思路,我们可以这样子设计: ①首先根据二分法找到vector某个target元素,这个元素一串target元素一个,记这个元素索引med。

    3.5K40

    leetcode34-排序数组查找元素一个最后一个位置

    前言 今天刷题目排序数组查找元素一个最后一个位置,这道题目最开始AC以后,然后做了优化操作,供大家参考。...题目 leetcode-34:排序数组查找元素一个最后一个位置 分类(tag):二分查找这一类 英文链接:https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array...找出给定目标值在数组开始位置结束位置。 你算法时间复杂度必须 O(log n) 级别。 如果数组不存在目标值,返回 [-1, -1]。...,也就是mid值4,这个下标可能最左4下标所以要记录保存一下; 观察这个数组,可以知道,最左4下标2,所以为了找到这个最左下标,需要令right值去等于mid-1;这样就把right...-1,如果不是-1,那说明需要继续找最右边下标,如果-1的话,那么说明数组没有target值,所以我们也不必去找最右边下标了,因为已经找过了,不存在,还费这事干嘛,最终这样优化完速度快了1ms

    2.6K30

    排序数组查找元素一个最后一个位置--题解

    排序数组查找元素一个最后一个位置 给定一个按照升序排列整数数组 nums,一个目标值 target。找出给定目标值在数组开始位置结束位置。...如果数组不存在目标值 target,返回 [-1, -1]。 进阶: 你可以设计并实现时间复杂度为 O(log n) 算法解决此问题吗?...] 示例 3: 输入:nums = [], target = 0 输出:[-1,-1] 提示: 0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 一个非递减数组...mid - 1 } else if nums[mid] == target { end = mid } else { start = mid + 1 } } //此处防止数组一个数...target int) int { start, end := 0, len(nums)-1 for start < end { //此处注意,为了防止 start=mid<end 导致死循环问题

    1.9K30
    领券