leetcode-php/src/leetcode/TwoSumLessThanK.php at master · imajinyun/leetcode-php · GitHub

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
<?php

declare(strict_types=1);

namespace leetcode;

class TwoSumLessThanK
{
    public static function twoSumLessThanK(array $nums, int $k): int
    {
        $ans = -1;
        if (empty($nums)) {
            return $ans;
        }
        $n = count($nums);
        for ($i = 0; $i < $n; $i++) {
            for ($j = 1; $j < $n; $j++) {
                $sum = $nums[$i] + $nums[$j];
                if ($sum < $k) {
                    $ans = max($ans, $sum);
                }
            }
        }

        return $ans;
    }

    public static function twoSumLessThanK2(array $nums, int $k): int
    {
        $ans = -1;
        if (empty($nums)) {
            return $ans;
        }
        sort($nums);
        [$ans, $l, $r] = [-1, 0, count($nums) - 1];
        while ($l <= $r) {
            $sum = $nums[$l] + $nums[$r];
            if ($sum < $k) {
                $ans = max($ans, $sum);
                $l++;
            } else {
                $r--;
            }
        }

        return $ans;
    }
}