Algorithm

15.3-sum

Description:

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

1
2
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

1
2
Input: nums = []
Output: []

Example 3:

1
2
Input: nums = [0]
Output: []

Constraints:

  • 0 <= nums.length <= 3000
  • $-10^5$ <= nums[i] <= $10^5$

Appropriate Answer (Sliding Window):

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
<?php

namespace LeetCode\ThreeSum;

class Solution
{

    /**
     * @param int[] $nums
     * @return int[][]
     */
    public function threeSum($nums)
    {
        $answer = [];
        $length = count($nums);

        if ($length < 3) {
            return $answer;
        }

        sort($nums);

        for ($i = 0; $i < $length - 2; $i++) {
            if ($i != 0 && $nums[$i - 1] == $nums[$i]) {
                continue;
            }

            $windowLeft = $i + 1;
            $windowRight = $length - 1;

            while ($windowLeft < $windowRight) {
                if ($nums[$i] + $nums[$windowLeft] + $nums[$windowRight] == 0) {
                    $answer[] = [$nums[$i], $nums[$windowLeft], $nums[$windowRight]];

                    $windowLeft++;
                    while (
                        $windowLeft < $windowRight &&
                        $nums[$windowLeft - 1] == $nums[$windowLeft]
                    ) {
                        $windowLeft++;
                    }

                    $windowRight--;
                    while (
                        $windowLeft < $windowRight &&
                        $nums[$windowRight + 1] == $nums[$windowRight]
                    ) {
                        $windowRight--;
                    }
                }

                if ($nums[$i] + $nums[$windowLeft] + $nums[$windowRight] < 0) {
                    $windowLeft++;
                    while (
                        $windowLeft < $windowRight &&
                        $nums[$windowLeft] == $nums[$windowLeft - 1]
                    ) {
                        $windowLeft++;
                        continue;
                    }

                    continue;
                }

                if ($nums[$i] + $nums[$windowLeft] + $nums[$windowRight] > 0) {
                    $windowRight--;
                    while (
                        $windowLeft < $windowRight &&
                        $nums[$windowRight] == $nums[$windowRight + 1]
                    ) {
                        $windowRight--;
                        continue;
                    }

                    continue;
                }
            }
        }

        return $answer;
    }
}

  • Time Complexity: $O(n^2)$

ʕ •ᴥ•ʔ：排序+選定第一個數字後，
創造出使用反向Sliding Window的情境。