服务器之家

服务器之家 > 正文

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

时间:2021-10-28 15:14     来源/作者:alpha

三数之和

给你一个包含 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-求解三数之和问题/

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部