Leetcode PHP题解--D104 167. Two Sum II - Input array is sorted

D104 167. Two Sum II - Input array is sorted

题目链接

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)资助。