关于PHP求解三数之和问题详析

吾爱主题阅读：126 2021-10-28 15:14:00 评论：0

三数之和

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

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

示例：

1 2 3 4 5 6 7 给定数组 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。逐个进行判断，并注意去重。有点类似于固定在一个值，然后剩下的用双指针求两数之和。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 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求解三数之和内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：http://hxd.best/2020/11/07/PHP-求解三数之和问题/

可以去百度分享获取分享代码输入这里。

声明

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，请转载时务必注明文章作者和来源，不尊重原创的行为我们将追究责任；3.作者投稿可能会经我们编辑修改或补充。