167. Two Sum II - Input array is sorted
给定一个已经排序好的整数数组,从中寻找两个数字,使其相加之后等于给定的一个数字。
返回这两个数字对应的下标。
首先想到的思路当然是逐个遍历,但是会超时。就不细说了。
之后想到的是用二分法找到小于目标数字的位置,用以减少遍历次数。
最后想到的是,把给定数组倒转过来,用isset去搜索是否存在指定加数。
<?php class Solution { /** * @param Integer[] $numbers * @param Integer $target * @return Integer[] */ function twoSum($numbers, $target) { $repeatItems = array_filter(array_count_values($numbers),function($v){ return $v>1; }); $vs = array_flip($numbers); foreach($vs as $k => $v){ if(isset($vs[$target-$k])){ if(isset($repeatItems[$target-$k])){ return [$v, $v+1]; } return [$v+1, $vs[$target-$k]+1]; } } return [null, null]; } }
若觉得本文章对你有用,欢迎用[爱发电](https://afdian.net/@skys215)资助。
我来评几句
登录后评论已发表评论数()