如何利用PHP實(shí)現(xiàn)三個(gè)數(shù)的總和

這篇文章運(yùn)用簡(jiǎn)單易懂的例子給大家介紹如何利用PHP實(shí)現(xiàn)三個(gè)數(shù)的總和，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

三數(shù)之和

給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請(qǐng)你找出所有滿足條件且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

示例：

給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，

滿足要求的三元組集合為：
[
 [-1, 0, 1],
 [-1, -1, 2]
]

來(lái)源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/3sum

解題思路 1

暴力枚舉法，三層 for + if 判斷就可以了，這樣作面試中 offer 會(huì)成為別人的。 不寫(xiě)代碼了，數(shù)據(jù)量大了也容易超時(shí)。

解題思路 2

可以先固定一個(gè)值，然后尋找后兩個(gè)值時(shí)可采取雙指針的方法，將總的時(shí)間復(fù)雜度優(yōu)化到 O(n^2)。

實(shí)現(xiàn)的過(guò)程中，要注意優(yōu)化以及去重。

首先我們先對(duì)原數(shù)組進(jìn)行排序，這樣可以把重復(fù)的值集中到一起，便于去重。

確定第一個(gè)元素時(shí)，如果它已經(jīng)比 0 大了，那么可以直接跳出循環(huán)，因?yàn)楹竺娴臄?shù)字都比它大。如 [1, 2, 3, 4], i = 0, nums[i] > 0, 這樣是不可能產(chǎn)生合法的情況的，直接 break。

確定第一個(gè)元素時(shí)，如果發(fā)現(xiàn)它與它前面的值一樣，那么跳過(guò)本輪。如 [-1, -1, 0, 1], 在第一輪后，已經(jīng)選出了 {-1, 0, 1}, 現(xiàn)在 i = 1，nums[i] == nums[i - 1], 為了避免重復(fù)，直接 continue。

接下來(lái)利用雙指針，left 指向 i + 1, right 指向 count($nums) - 1。逐個(gè)進(jìn)行判斷，并注意去重。有點(diǎn)類(lèi)似于固定在一個(gè)值，然后剩下的用雙指針求兩數(shù)之和。

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; // 第一個(gè)數(shù)大于 0，后面的數(shù)都比它大，肯定不成立了

  if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue; // 去掉重復(fù)情況

  $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]];

   // 現(xiàn)在要增加 left，減小 right，但是不能重復(fù)，比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后，需要排除重復(fù)的 -1 和 3

   $left++;
   $right--; // 首先無(wú)論如何先要進(jìn)行加減操作

   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;
 }
}

關(guān)于如何利用PHP實(shí)現(xiàn)三個(gè)數(shù)的總和就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。