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

给定一个数组,查找其和等于给定和的元素对,并返回其索引之和

解决这个问题可以使用双指针的方法。首先对数组进行排序,然后使用两个指针,一个指向数组的起始位置,一个指向数组的末尾位置。比较指针所指向的两个元素的和与给定和的大小关系,如果和小于给定和,则将左指针向右移动一位;如果和大于给定和,则将右指针向左移动一位;如果和等于给定和,则找到了一对元素。将找到的元素的索引相加即可得到索引之和。

以下是示例代码:

代码语言:txt
复制
def find_pairs(nums, target):
    # 对数组进行排序
    nums.sort()
    # 初始化左右指针
    left = 0
    right = len(nums) - 1
    # 存储结果的列表
    pairs = []
    
    while left < right:
        # 计算当前两个元素的和
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            # 找到一对元素,将索引之和添加到结果列表中
            pairs.append(left + right)
            # 继续寻找下一对元素
            left += 1
            right -= 1
        elif current_sum < target:
            # 和小于给定和,将左指针向右移动一位
            left += 1
        else:
            # 和大于给定和,将右指针向左移动一位
            right -= 1
    
    return pairs

这段代码的时间复杂度为O(nlogn),其中n为数组的长度。在最坏情况下,需要遍历整个数组,因此空间复杂度为O(1)。

这个问题的应用场景可以是在给定一组数字的情况下,查找其中两个数字的和等于给定值的情况。例如,在一个交易系统中,需要找到两笔交易的金额之和等于某个目标金额,以实现特定的交易策略。

腾讯云提供了多个与云计算相关的产品,其中包括云服务器、云数据库、云存储等。您可以根据具体的需求选择适合的产品。以下是腾讯云相关产品的介绍链接:

  • 腾讯云服务器:提供弹性计算能力,支持多种操作系统和应用场景。
  • 腾讯云数据库:提供高性能、可扩展的数据库服务,包括关系型数据库和NoSQL数据库。
  • 腾讯云对象存储:提供安全可靠的云存储服务,适用于存储和管理各种类型的数据。
  • 腾讯云函数计算:无服务器计算服务,支持按需运行代码,无需管理服务器。
  • 腾讯云人工智能:提供多种人工智能服务,包括图像识别、语音识别、自然语言处理等。
  • 腾讯云物联网:提供物联网设备接入、数据管理和应用开发的解决方案。
  • 腾讯云移动开发:提供移动应用开发和运营的云服务,包括推送、分析、测试等功能。
  • 腾讯云区块链:提供基于区块链技术的解决方案,包括区块链服务和区块链托管等。
  • 腾讯云元宇宙:提供虚拟现实和增强现实的开发和应用服务。

请注意,以上链接仅供参考,具体选择产品时需要根据实际需求进行评估。

相关搜索:给定一个未排序的数组,如何删除重复项并对其进行排序?查找、更新元素并更改其在对象数组中的索引从矩阵中找出一些行的算法,其和等于给定行查找(或生成)所有可能的(给定长度的)等于给定和的正数组合。(Python)在python数组中查找接近数字的值并对其进行索引如何在数组中找到和等于或小于并接近给定值的元素?如何根据给定的索引和条件开始对特定列表元素进行计数?如何获取数组中的一个元素并对其进行样式设置?在给定行和列索引数组的情况下,Numpy选择元素给定DxN数组A和B,求出其欧几里德距离s.t。AB=L2(A[i,:]-B[:,j])的ijth元素给定一个多维数组,返回一个包含对角线和的数组查找文本字段的特定id和类并对其执行document.write操作在Ruby中,如何在给定要中断字符串的索引数组的情况下对其进行中断?在给定通用维度的开始和结束索引的情况下对NumPy数组进行切片给定一个正整数数组,找到长度为L的连续子序列的起始索引,它们的和等于SVBA,查找列(C)中的最高值并返回其值和相邻单元格值如何使用DOM选择html文件的元素(第一个和最后一个除外)并对其进行操作?给定一个元素A,从python中的列表中查找A的前一个和下一个元素给定数组,编写一个函数来查找最大值并返回匹配的字符串给定一个整数数组,返回一个新数组,使得索引i处的每个元素……代码不起作用
相关搜索:
页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

【JavaScript】内置对象 - 数组对象 ④ ( 索引方法 | 查找给定元素一个索引 | 查找给定元素最后一个索引 | 索引方法案例 - 数组元素去重 )

文章目录 一、索引方法 1、查找给定元素一个索引 - indexOf() 2、查找给定元素最后一个索引 - lastIndexOf() 二、索引方法案例 - 数组元素去重 1、需求分析 2、代码实现...一、索引方法 1、查找给定元素一个索引 - indexOf() 调用 Array 数组对象 indexOf() 方法 可以 查找给定元素一个索引 , 语法如下 : indexOf(searchElement...该索引值 ; 返回值 就是 在数组中 第一个 被找到 指定元素 索引位置 , 如果没有找到返回 -1 ; 参考文档 : https://developer.mozilla.org/zh-CN/docs...- lastIndexOf() 调用 Array 数组对象 lastIndexOf() 方法 可以 查找给定元素最后一个索引 , 语法如下 : lastIndexOf(searchElement...给定一个数组 , [9, 5, 2, 7, 5] 将数组重复元素删除 , 也就是将上述数组中 重复元素 5 删除 ; 创建一个数组 , 遍历旧数组 , 遍历每个旧数组元素时 , 查询该元素是否在新数组

16110

大厂算法面试:使用移动窗口查找两个不重叠且元素等于给定数组

我们看看这次题目: 给定一个所有元素都是正整数数组,同时给定一个值target,要求从数组中找到两个不重叠数组,使得各自数组元素等于给定数值target,并且要求两个数组元素个数之和最小,例如给定数组为...[1 , 2, 1, 1, 1],同时给定目标值3,此时它有三个子数组分别为[1,2], [2,1],[1,1,1],他们元素等于3,但是由于前两个数组有重叠,因此满足条件两个子数组为[1,2]...使用滑动窗口我们能方便找到元素等于给定数组。注意到数组只包含正整数,因此如果保持start不变,end向右边移动,那么窗口内部元素就会变大,如果保持end不变,那么窗口内元素就会减小。...让end继续向右移动一个单位,此时窗口内元素为[1,2,1],元素为4大于给定值,于是我们让start向左挪动一个单位,得到子数组[2,1],此时我们又找到了满足条件数组。...如此类推,我们从数组最左端出发,如果窗口内元素小于给定指定值,那么就向右移动end,如果大于给定值,那么就像左移动一个单位,当窗口挪出数组,也就是end值大于数组最后一个元素下标时,查找结束,当前能找到所有满足元素等于特定值所有子数组

1.6K20
  • 关于一个数组中两个数等于给定问题

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

    75920

    python面试题-【二分法查找给定一个已排序非重复整数数组一个目标值,如果找到目标,则返回索引

    前言 给定一个已排序非重复整数数组一个目标值,如果找到目标,则返回索引。如果不是,返回索引按顺序插入时位置。 题目 给定一个已排序非重复整数数组一个目标值,如果找到目标,则返回索引。...如果不是,返回索引按顺序插入时位置。...但是,二分查找时候一定要是有序数组。 二分法思想 1.首先从数组中间元素开始查找,如果该元素正好是目标元素,则搜索结束,否则执行下一步。...2.如果目标元素大于/小于中间元素,则在数组大于/小于中间元素那一半区域查找,然后重复步骤1操作。...3.如果某一步数组为空,则表示找不到目标元素 如下图,数组中有目标元素查找21 如下图,数组中没有目标元素查找70 直到 low > high 查找失败 python3 二分法查找 python3

    84820

    【算法】哈希表 ( 两数之和 )

    HashSet 或 HashMap 即可 ; 一、两数之和 ---- 两数之和 : https://www.lintcode.com/problem/56/ 给定一个未排序数组 , 找到数组两个元素之和..., 等于给定 target 值 ; 该问题最直观解法 , 就是 蛮力算法 ; 如 : 给定数组 [6, 4, 2, 9] , 给定 target 值为 10 , 找出数组中哪两个元素之和为 10..., 外层循环遍历数组元素 , 内层循环遍历 target - 数组元素 值是否在数组中 ; 上述算法事件复杂度为 O(n^2) ; 这里内层循环中 , 检测一个数字是否在数组中 , 可以使用 哈希表...索引作为 Value 值 ; 上述操作 , 一边遍历 , 一边将数组元素插入到哈希表中 , [3, 6, 2, 4] , 在遍历到 6 时 , 从哈希表中查找 10 - 6 = 4 这个值 , 哈希表中没有...i 索引值 // 如果正在遍历 numbers[j], 恰好等于某个 target - numbers[i] // 说明 i, j 就是要找两个索引

    74120

    2021-07-30:两个有序数组间相加Topk问题。给定两个有序数组arr1arr2,再给定一个整数k,返回来自arr1

    2021-07-30:两个有序数组间相加Topk问题。给定两个有序数组arr1arr2,再给定一个整数k,返回来自arr1arr2两个数相加最大前k个,两个数必须分别来自两个数组。...2.我方法。小根堆。两个有序数组构成一个二维数组。然后从右下往左上遍历,当遍历数量大于等于k时,停止遍历。见图。 时间复杂度:略大于O(k)。 空间复杂度:O(k)。 ? 代码用golang编写。...9, 11} topK := 4 if true { ret := topKSum1(arr1, arr2, topK) fmt.Println("左神方法...) } } type Node struct { index1 int // arr1中位置 index2 int // arr2中位置 sum int //...arr1[index1] + arr2[index2]值 } func NewNode(i1 int, i2 int, s int) *Node { ret := &Node{}

    79250

    2022-04-17:给定一个数组arr,其中值有可能正、负、0,给定一个正数k。返回累加>=k所有子数组中,最短数组长度。来自字节跳动。力扣8

    2022-04-17:给定一个数组arr,其中值有可能正、负、0, 给定一个正数k。 返回累加>=k所有子数组中,最短数组长度。 来自字节跳动。力扣862。...答案2022-04-17: 看到子数组,联想到结尾怎么样,开头怎么样。 预处理前缀,单调栈。 达标的前缀,哪一个离k最近? 单调栈+二分。复杂度是O(N*logN)。 双端队列。...} let mut l: isize = 0; let mut r: isize = 0; for i in 0..N + 1 { // 头部开始,符合条件,...ans = get_min(ans, i as isize - dq[l as usize]); l += 1; } // 尾部开始,前缀比当前前缀大于等于

    1.4K10

    【数据结构算法】寻找数组中心下标

    一、题目描述 给你一个整数数组 nums ,请计算数组 中心下标 。 数组 中心下标 是数组一个下标,左侧所有元素相加等于右侧所有元素相加。...如果中心下标位于数组最左端,那么左侧数之和视为 0 ,因为在下标的左侧不存在元素。这一点于中心下标位于数组最右端同样适用。 如果数组有多个中心下标,应该返回 最靠近左边 一个。...2.1.2 寻找数组中第 k 大元素 题目描述:给定一个无序数组一个整数k,找到数组中第k大元素。 解题思路:可以使用前缀和和快速选择算法来解决这个问题。首先,计算出数组前缀。...如果枢轴左边元素个数小于k,则在左边数组中继续查找;如果枢轴左边元素个数大于等于k,则在右边数组中继续查找。最后,当找到第k小元素时,返回元素即可。...初始化时,相当于索引 i=−1 ,此时 leftSum = 0 , rightSum = 所有元素 。 需要考虑大数越界问题。题目给定整数数组 nums ,给定取值范围。

    13710

    2021-05-13:数组中所有数都异或起来结果,叫做异或给定一个数组arr,返回arr最大子数组异或

    2021-05-13:数组中所有数都异或起来结果,叫做异或给定一个数组arr,返回arr最大子数组异或。 前缀树。一个数,用二进制表示,0走左边分支,1走右边分支。 时间复杂度:O(N)。...结构 // nexts[0] -> 0方向路 // nexts[1] -> 1方向路 // nexts[0] == null 0方向上没路!...= null 0方向有路,可以跳下一个节点 // nexts[1] == null 1方向上没路! // nexts[1] !...= null 1方向有路,可以跳下一个节点 type Node struct { nexts []*Node } func twoSelectOne(condition bool, a int...谁 ^ 最大结果(把结果返回) func (this *NumTrie) maxXor(num int) int { cur := this.head ans := 0 for

    41530

    给定两个数组 quality wage , 其中,quality 表示第 i 名工人工作质量,最低期望工资

    给定两个数组 quality wage ,其中,qualityi 表示第 i 名工人工作质量,最低期望工资为 wagei 。现在我们想雇佣 k 名工人组成一个工资组。...在雇佣 一组 k 名工人时,我们必须按照下述规则向他们支付工资:工资组中每名工人,应当按工作质量与同组其他工人工作质量比例来支付工资。工资组中每名工人至少应当得到他们最低期望工资。...给定整数 k ,返回 组成满足上述条件付费群体所需最小金额。输入: quality = 10,20,5, wage = 70,50,30, k = 2。输出: 105.00000。...3.维护一个大小为 k 小根堆,表示当前最低期望工资组中 k 名工人工作质量。4.遍历所有员工,如果堆未满,则将该员工加入堆中更新最低期望工资。...如果堆已满,则检查当前员工能否替换堆顶元素,如果可以,则弹出堆顶元素并将当前员工入堆,更新最低期望工资。5.最终返回最低期望工资即可。

    20300

    2022-04-25:给定一个整数数组返回所有数之间第 k 个最小距离。一 (A, B) 距离被定义为 A B 之间绝对差值。

    2022-04-25:给定一个整数数组返回所有数之间第 k 个最小距离。一 (A, B) 距离被定义为 A B 之间绝对差值。...输入: nums = [1,3,1] k = 1 输出:0 解释: 所有数如下: (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 因此第 1 个最小距离是 (1,1),它们之间距离为...找出第 k 小距离。 答案2022-04-25: 排序。二分法,f(x)是小于等于x个数。刚刚大于等于k。 f(x)不回退窗口。...r = dis - 1; } else { l = dis + 1; } } return ans; } // <= dis数字...,有几个,返回 fn f(arr: &mut Vec, dis: isize) -> isize { let mut cnt: isize = 0; let mut l:

    46020

    2022-04-23:给定一个整数数组 nums 我们要将 nums 数组每个元素移动到 A 集合 或者 B 集合中 使得 A 集合 B 集合不为空,

    2022-04-23:给定一个整数数组 nums我们要将 nums 数组每个元素移动到 A 集合 或者 B 集合中使得 A 集合 B 集合不为空,并且 average(A) == average...答案2022-04-23:定义全局变量 n、s、l r,分别表示数组长度、数组元素之和、左侧集合元素个数右侧集合元素个数。...编写函数 splitArraySameAverage(nums []int) bool,其中 nums 是输入整数数组。首先检查数组长度是否为 1,如果是则返回 false。计算数组元素之和 s。...调用函数 collect(larr, true) 收集左侧集合指标值,调用函数 collect(rarr, false) 收集右侧集合指标值。右侧集合指标值进行排序,以便进行二分查找。...如果 index 等于数组长度,则计算指标值并将其存储在 lvalues 或 rvalues 中。对于每个元素,都有两种选择:不加入集合(包括左侧集合右侧集合),或者加入集合并递归到下一个元素

    63700

    几道散列(哈希)表有关面试题

    题目描述 给定一个整数数组 nums 一个目标值 target,请你在该数组中找出为目标值那 两个 整数,返回他们数组下标。 你可以假设每种输入只会对应一个答案。...首先设置一个 map 容器 record 用来记录元素值与索引,然后遍历数组 nums 。...每次遍历时使用临时变量 complement 用来保存目标值与当前值差值 在此次遍历中查找 record ,查看是否有与 complement 一致值,如果查找成功则返回查找索引值与当前变量值...建立一个 256 位大小整型数组 freg ,用来建立字符出现位置之间映射。 维护一个滑动窗口,窗口内都是没有重复字符,去尽可能扩大窗口大小,窗口不停向右滑动。...首先当取出第十个字符时,将其存在哈希表里,该字符串出现频率映射,之后每向左移三位替换一个字符,查找新字符串在哈希表里出现次数,如果之前刚好出现过一次,则将当前字符串存入返回数组并将其出现次数加一,

    1.4K20

    你管这破玩意叫“撞指针”?

    两数之和 II - 输入有序数组 给定一个已按照升序排列整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。...函数应该以长度为 2 整数数组形式返回这两个数下标值。...要从数组中找出两个数满足之和等于目标数,最直观解法就是通过暴力枚举。两层遍历数组所有的下标 i j ,再判断对应数组元素是否等于目标数,找到则直接返回,否则就无解。...0; i < numbersSize; ++i) { for (int j = i + 1; j < numbersSize; ++j) { /* 双层遍历,查找数组中是否存在两个元素等于目标值...答案是有的,这就是今天要讲撞指针”。 ? 撞指针 撞指针:在有序数组中,定义指向最左侧索引为左指针(left),最右侧为右指针(right),然后从数组两头向中间进行遍历。

    35920

    Python数组中求和问题

    本文主要内容是通过001问题来初步了解数组求和两种常用方法。 001-Two Sum 给定一个整数数组一个目标值,找出数组中和为目标值两个数。...哈希 (1) O(n) (2) 考虑暴力循环中我们做事情,我们先挑出一个值a,然后看数组中其他值是否能与值a相加等于目标,也可以说成看数组中是否存在一个等于目标值减去值a。...回到题目中: (1) 由于需要返回索引,所以我们必须存储两个数组一个是无序(用于查找真实索引),另一个是有序(用于查找符合题目的值)。...(2) 两个指针leftright分别指向数组中第一个元素最后一个元素(最小值最大值) (3) 循环结束条件为左指针大于等于右指针(左边不能比右边大,而且一个元素只能用一次) (4) 然后就判断左值...(5) 当等于时由于我们需要得到左值右值在原本数组索引,我们需要考虑以下问题。

    2.6K00

    2022-04-25:给定一个整数数组返回所有数之间第 k 个最小距离。一 (A, B) 距离被定义为 A B 之间绝对差值。 输入: nums

    2022-04-25:给定一个整数数组返回所有数之间第 k 个最小距离。一 (A, B) 距离被定义为 A B 之间绝对差值。...输入: nums = 1,3,1 k = 1 输出:0 解释: 所有数如下: (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 因此第 1 个最小距离是 (1,1),它们之间距离为...找出第 k 小距离。 答案2022-04-25: 排序。二分法,f(x)是小于等于x个数。刚刚大于等于k。 f(x)不回退窗口。...r = dis - 1; } else { l = dis + 1; } } return ans; } // <= dis数字...,有几个,返回 fn f(arr: &mut Vec, dis: isize) -> isize { let mut cnt: isize = 0; let mut l:

    56730
    领券