leetcode地址:https://leetcode-cn.com/problems/two-sum/description/
题目:
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
解决方案:
<?php $nums = array(2, 7,15, 11, 1,33,1); $target =172; $res=twoSum2($nums,$target); var_dump($res); //===============================方法1=============================== //暴力法 //1.将第一个数与数组中的每个数相加,看是否等于target //2.如果等于,返回。反之,继续循环 //3.然后第二个数与数组中每个数相加... function twoSum($nums,$target) { for ($i=0;$i<count($nums);$i++){ for ($j=$i+1;$j<count($nums);$j++){ if ($nums[$i]+$nums[$j]==$target){ return array($i,$j); } } } return "没有匹配的数据"; } //===============================方法2=============================== //双指针法 //1.需要2个数组,一个是原数组(查找值),一个是对原数组排序后的数组(查找索引) //2.两个指针,left和right(最小值和最大值) //3.循环条件为左指针大于右指针,如果左指针等于右指针,说明没有找到匹配的数据 //4.左指针下标的数+右指针下标的数>target,右指针下标-1 //5.左指针下标的数+右指针下标的数<target,左指针下标+1 // 1,4,8,12 target=12 // 1+12>12 右指针下标-1 (假如是左指针+1,则为4+12。❌) // 1+8<12 左指针下标+1 (假如是右指针-1,则为1+4。 ❌) // 4+8=12 //6.通过array_search根据值查找对应的下标 function twoSum2($nums,$target) { $raw_nums=$nums; sort($nums); $left=0; $right=count($nums)-1; while($left<$right) { $V_left=$nums[$left]; $V_right=$nums[$right]; $two_sum=$V_left+$V_right; echo $V_left."----".$V_right."<br/>"; if ($two_sum>$target) { $right-=1; }elseif ($two_sum<$target) { $left+=1; }else {return array(array_search($V_left,$raw_nums),array_search($V_right,$raw_nums)); } if ($left==$right) { return '没有匹配的数据'; } } }
知识点补充站:
- for循环https://doc.yonyoucloud.com/doc/PracticalPHP/Introducing_PHP/How_PHP_is_written/loops.html
- 嵌套循环https://doc.yonyoucloud.com/doc/PracticalPHP/Introducing_PHP/How_PHP_is_written/loops_within_loops.html
- sort排序http://php.net/manual/zh/function.sort.php
- array_search根据值返回他的键名http://www.w3school.com.cn/php/func_array_search.asp
在学习该算法时遇到的问题
- 方法名为什么不能用public?(咦,这个错误犯的有点弱智了,好吧,原谅自己是个小白- -!)因为public,private,protected只能在class(类)中使用
- sort排序时千万不能写$rs=sort($data);因为返回的是一个布尔值,排序成功还是失败
总结:
主要通过循环解决此问题,可分为单指针和双指针方法,及哈希(看了一轮,不大懂哈希,日后在补充哈希的解法)