PHP怎样实现求三个数之和的问题?

这篇文章给大家分享的是一个简单的PHP示例，也就是实现三个数求和的问题，这个问题很多PHP初学者都会遇到，因此分享给大家参考一下，文中示例代码介绍的非常详细，感兴趣的朋友接下来跟随小编一起学习一下吧。

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
 [-1, 0, 1],
 [-1, -1, 2]
]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/3sum

解题思路 1

暴力枚举法，三层 for + if 判断就可以了，这样作面试中 offer 会成为别人的。 不写代码了，数据量大了也容易超时。

解题思路 2

可以先固定一个值，然后寻找后两个值时可采取双指针的方法，将总的时间复杂度优化到 O(n^2)。

实现的过程中，要注意优化以及去重。

首先我们先对原数组进行排序，这样可以把重复的值集中到一起，便于去重。

确定第一个元素时，如果它已经比 0 大了，那么可以直接跳出循环，因为后面的数字都比它大。如 [1, 2, 3, 4], i = 0, nums[i] > 0, 这样是不可能产生合法的情况的，直接 break。

确定第一个元素时，如果发现它与它前面的值一样，那么跳过本轮。如 [-1, -1, 0, 1], 在第一轮后，已经选出了 { -1, 0, 1} , 现在 i = 1，nums[i] == nums[i - 1], 为了避免重复，直接 continue。

接下来利用双指针，left 指向 i + 1, right 指向 count($nums) - 1。逐个进行判断，并注意去重。有点类似于固定在一个值，然后剩下的用双指针求两数之和。

class Solution {


 /** * @param Integer[] $nums * @return Integer[][] */
 function threeSum($nums) {
    
 $result = [];
    
 $count = count($nums);
    
 if ($nums === null || count($nums) = 2) return $result;
    

 sort($nums);
     // O(nlogn)

 for ($i = 0;
     $i  $count - 2;
 $i++) {
     // O(n^2)

  if ($nums[$i] >
     0) break;
     // 第一个数大于 0，后面的数都比它大，肯定不成立了

  if ($i >
     0 &
    &
     $nums[$i] === $nums[$i - 1]) continue;
     // 去掉重复情况

  $target = -$nums[$i];
    
  $left = $i + 1;
    
  $right = $count - 1;

  while ($left  $right) {

  if ($nums[$left] + $nums[$right] === $target) {
    
   $result[] = [$nums[$i], $nums[$left], $nums[$right]];
    

   // 现在要增加 left，减小 right，但是不能重复，

//比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重复的 -1 和 3

   $left++;
    
   $right--;
     // 首先无论如何先要进行加减操作

   while ($left  $right &
    &
     $nums[$left] === $nums[$left - 1]) $left++;
    
   while ($left  $right &
    &
     $nums[$right] === $nums[$right + 1]) $right--;

  }
 else if ($nums[$left] + $nums[$right]  $target) {
    
   $left++;

  }
 else {
     // $nums[$left] + $nums[$right] >
     $target

   $right--;

  }

  }

 }
    

 return $result;

 }

}
    

以上就是关于PHP实现求三个数之和的介绍啦，本文只是提供了几种实现思路，代码仅供参考，需要的朋友可以了解看看，希望对大家学习PHP有帮助，想要了解更多可以继续浏览网络其他相关的文章。

文本转载自脚本之家

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！