前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >求一个数组中和为指定值的2个元素下标值

求一个数组中和为指定值的2个元素下标值

作者头像
一个架构师
发布2022-06-20 19:40:55
7430
发布2022-06-20 19:40:55
举报
文章被收录于专栏:从码农的全世界路过

如何求得一个数组中和为指定值的2个元素下标?

例:数组num={2, 7, 17, 26, 27, 31, 41, 42, 55, 80} target=72.求得元素下标值为:{5,6}

首先分析一下:

1. 这个数组并不是有序数组,这就排除了搜索空间缩减方法.有序数列查找方式可以参考如何从有序数组中找到和为指定值的两个元素下标

2. 如果使用暴力遍历方式,那时间复杂度会是O(n^2),有些大,需要换种思路,减少时间复杂度.

3. 要找到对应元素下标,不是元素值,所以使用排序方式,会打乱原有下标值.

整理下思路,因为数组是无序的,所以想知道两数之和是指定值,必须要遍历数组,那时间复杂度,至少会是O(n);

遍历到一个数时,另一个数也可以根据x=target-n计算出来,那问题焦点转换为判断另一数是否存在于数组中,遍历过的,我们不想重新遍历,需要合理的数据结构记录下;未遍历过的,可以在遍历到时,再次使用这条规则.

什么样的数据结构适合呢?

哈希结构! 时间复杂度为O(1).

根据这个思路,我们看下代码:

代码语言:javascript
复制
int[] sum2Num(int[] nums, int target) {
        int length = nums.length;
        Map<Integer, Integer> map = new HashMap<>(length);
        for (int i = 0; i < length; i++) {
            Integer n = nums[i];
            Integer otherNum = target - n;
            if (map.containsKey(otherNum)) {
                // bingo
                return new int[]{i, map.get(otherNum)};
            }
            map.put(n, i);
        }
        return new int[]{};
    }

总结一下,使用map结构是空间换时间,提升时间复杂度.

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 从码农的全世界路过 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档