主頁 > 知識庫 > 關(guān)于PHP求解三數(shù)之和問題詳析

關(guān)于PHP求解三數(shù)之和問題詳析

熱門標簽:黔江400電話如何辦理 400電話鄭州申請 中原區(qū)電話機器人價格 招標自動語音外呼系統(tǒng) OMG地圖標注app gps 地圖標注軟件 ai電話機器人加盟代理 電銷機器人便宜的有嗎 地圖標注視頻廣告入駐

三數(shù)之和

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

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

示例:

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

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

來源:力扣(LeetCode) 鏈接:https://leetcode-cn.com/problems/3sum

解題思路 1

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

解題思路 2

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

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

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

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

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

接下來利用雙指針,left 指向 i + 1, right 指向 count($nums) - 1。逐個進行判斷,并注意去重。有點類似于固定在一個值,然后剩下的用雙指針求兩數(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; // 第一個數(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--; // 首先無論如何先要進行加減操作

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

參考鏈接:

  • 三數(shù)之和的官方題解和高贊答案
  • 極客時間 算法面試通關(guān)40講

到此這篇關(guān)于PHP求解三數(shù)之和問題的文章就介紹到這了,更多相關(guān)PHP求解三數(shù)之和內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

標簽:日照 北京 濟源 池州 哈密 孝感 阿里 那曲

巨人網(wǎng)絡(luò)通訊聲明:本文標題《關(guān)于PHP求解三數(shù)之和問題詳析》,本文關(guān)鍵詞  關(guān)于,PHP,求解,三數(shù),之和,;如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題,煩請?zhí)峁┫嚓P(guān)信息告之我們,我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò),涉及言論、版權(quán)與本站無關(guān)。
  • 相關(guān)文章
  • 下面列出與本文章《關(guān)于PHP求解三數(shù)之和問題詳析》相關(guān)的同類信息!
  • 本頁收集關(guān)于關(guān)于PHP求解三數(shù)之和問題詳析的相關(guān)信息資訊供網(wǎng)民參考!
  • 推薦文章