How to solve the sum of three numbers problem in PHP

Give you an array nums containing n integers, determine whether there are three elements a, b, c in nums, such that a b c=0? What should we do when we encounter this kind of problem? Today I will take you through it.

Given you an array nums containing n integers, determine whether there are three elements a, b, c in nums such that a b c = 0? Please find all triples that meet the conditions and are not repeated.

Note: Answers cannot contain duplicate triples.

Example:

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：[
 [-1, 0, 1],
 [-1, -1, 2]]

Problem-solving ideas 1

Violent enumeration method, three-layer for if judgment is enough, this way you can make an offer in the interview will become someone else’s. If you don’t write code anymore, it will easily time out if the amount of data is large.

Problem-solving idea 2

You can fix a value first, and then use a double pointer method to find the last two values ​​to optimize the total time complexity to O(n^2).

During the implementation process, attention should be paid to optimization and deduplication.

First we sort the original array, so that duplicate values ​​can be gathered together to facilitate deduplication.

When determining the first element, if it is already greater than 0, you can jump out of the loop directly, because the subsequent numbers are all greater than it. For example, [1, 2, 3, 4], i = 0, nums[i] > 0, it is impossible to produce a legal situation, so just break.

When determining the first element, if it is found to be the same as the value before it, skip this round. For example, [-1, -1, 0, 1], after the first round, {-1, 0, 1} has been selected, now i = 1, nums[i] == nums[i - 1], To avoid duplication, continue directly.

Next use double pointers, left points to i 1, right points to count($nums) - 1. Make judgments one by one and pay attention to removing duplicates. It's a bit like fixing on a value, and then using two pointers to find the sum of the two numbers.

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

Recommended learning: php video tutorial

The above is the detailed content of How to solve the sum of three numbers problem in PHP. For more information, please follow other related articles on the PHP Chinese website!