栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

算法第六天(简单)两数之和Ⅱ-输入有序数组

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法第六天(简单)两数之和Ⅱ-输入有序数组

题目描述:

给定一个已按照 非递减顺序排列  的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

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

题目分析:

题目中明确给出,需要将两个数相加并满足目标书,但是在输出的时候,他又额外的添加了一个要求,下标要从1开始,但是数组都是从0开始的,这个是好解决的,只要在最后的输出加1即可

解题思路分析:

他要求将数组中的两个数相加,那么我需要找到两个数,其和为目标数,可以使用双指针来做这道题目,将双指针的值相加,判断是否等于target,大了,改变高位指针,小了,改变低位指针

代码如下:

var twoSum = function(numbers, target) {
    let low = 0;
    let high = numbers.length-1;

    while(low target) {
            high--
        }else {
            low++;
        }
    }
};

但是一开始我并不是这样做的,我是使用两个嵌套的for循环,将其暴力解出,具体思路如下:

第一层的for循环是用来控制第一个需要求出的值的,第二个for循环是用来求第二个需要求出的值,但是在求解的过程中,我发现这样的方法又需要添加很多的“补丁”,因为里面的for循环我是使用了双指针的,所以说当这个循环结束的时候,我需要重置指针的值,不然指针的值会不断的变化,无法得出我想要的结果,下面是我第一次的代码:

        var twoSum = function(numbers,target) {
            let n=numbers.length;
            let low=0,high=n-1;
            let array1=[],a,b;
            for(i=0;itarget){
                        high--
                    }else{
                        high++
                    }
                }
                high=n-1
                low++
            }
        };

但是这样做,时间复杂度过高,最后也能解出,但是这毕竟是一道算法的题目,会超出时间的限制,我们对于时间是有要求的,所以不能够使用这个方法。

总结反思:

也许是因为才刚刚开始练习算法的原因,我发现自己特别喜欢使用for循环来暴力解决办法,其实这道题不是很困难,承认使用暴力能够解决问题,但是这样的方法不但复杂,而且实用性比较低,所以需要刻意的回避使用for循环,还有对于双指针的理解,总是喜欢通过将双指针平均化来判断,其实这样也无形中增加了题目的难度,综上,以后练习算法,需要刻意回避使用for循环

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/665499.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号