PHP에서 세 숫자의 합 문제를 해결하는 방법

n개의 정수를 포함하는 nums 배열이 주어졌을 때, a+b+c=0이 되는 세 개의 요소 a, b, c가 num에 있는지 확인하세요. 이런 문제가 발생하면 어떻게 해야 합니까? 오늘은 그 문제를 해결해 드리겠습니다.

n개의 정수를 포함하는 nums 배열이 주어지면 nums에 a + b + c = 0이 되는 세 개의 요소 a, b, c가 있는지 확인하세요. 조건을 만족하고 반복되지 않는 트리플을 모두 찾아보세요.

참고: 답변에 중복된 트리플은 허용되지 않습니다.

예:

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

문제 해결 아이디어 1

폭력적인 열거 방법, +에 대한 3단계 판단이 충분하면 면접 제안이 ​​다른 사람의 것이 됩니다. 더 이상 코드를 작성하지 않으면 데이터 양이 많으면 타임아웃되기 쉽습니다.

문제 해결 아이디어 2

먼저 값을 수정한 다음 이중 포인터 방법을 사용하여 마지막 두 값을 찾아 총 시간 복잡도를 O(n^2)로 최적화할 수 있습니다.

구현 과정에서는 최적화와 중복 제거에 주의를 기울여야 합니다.

먼저 중복 제거를 용이하게 하기 위해 중복 값을 그룹화할 수 있도록 원본 배열을 정렬합니다.

첫 번째 요소를 결정할 때 이미 0보다 큰 경우 후속 숫자가 모두 0보다 크므로 루프에서 직접 점프할 수 있습니다. 예를 들어 [1, 2, 3, 4], i = 0, nums[i] > 0이면 합법적인 상황을 연출할 수 없으므로 그냥 중단하세요.

첫 번째 요소를 결정할 때 이전 값과 동일한 것으로 확인되면 이번 라운드를 건너뜁니다. 예를 들어 [-1, -1, 0, 1], 첫 번째 라운드 이후 {-1, 0, 1}이 선택되었으므로 이제 i = 1, nums[i] == nums[i - 1], 중복을 피하려면 직접 계속하세요.

다음으로 이중 포인터를 사용하고 왼쪽 포인트는 i + 1을 가리키고 오른쪽 포인트는 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 비디오 튜토리얼

위 내용은 PHP에서 세 숫자의 합 문제를 해결하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!