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

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

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

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

今天学习了一下碰撞指针的用法,就写了这道经典的题目

题目如下:

给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。

LeetCode.167


一开始我就想到了碰撞指针,但是不知道为什么我的时间复杂度非常高,
先讲一下我的思路:
定义两个指针,L指向nums[ 0 ] ,R 指向 num[ len-1 ],然后在保证L 小于
R的情况下,如果比 target 小就L++,大就R–,否则返回

这里有两个难点:
1.由于有重复的元素,如何保证R已经指向某元素的第一个位置?
我们可以增加判断条件
if(nums[R] + nums[L] == target && nums[R] != num[R-1])
2.这样又会出现一个问题,那就是如果两个目标元素相邻且相等怎么办?
我又进行了特判,并修改上面的代码

if(numbers[l] + numbers[r] == target && numbers[r] != numbers[r-1] && r - l > 1)
           { 
               return {l+1,r+1};
           }
           else if(numbers[l] + numbers[r] == target  && r - l == 1){
             return {l+1,r+1};
           }

感觉代码十分的臃肿。于是我看了一下官方的答案:

class Solution {
public:
    vector twoSum(vector& numbers, int target) {
        int low = 0, high = numbers.size() - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return {low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return {-1, -1};
    }
};

我发现我把题目想复杂了,我的理解是:
比如数组为:

1 2 32 40 40 40 42 43

然后 target = 41,然后我们的返回值为[1,4];
但是题目的意思是不会出现这种情况,只会有两个固定的位置的和为target。

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

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

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