溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章運用簡單易懂的例子給大家介紹如何利用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實現三個數的總和就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
