双指针

发表于 | 分类于 ， | 本文总阅读量

题目一

删除排序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function removeDuplicates(&$nums) {
        $length = count($nums);
        $i = 0;
        for($j = 1;$j<$length;$j++) {
            if ($nums[$j] != $nums[$i]) {
                $i++;
                $nums[$i] = $nums[$j];
            }
        }
        return $i + 1;
    }
}

题目二

删除链表的倒数第N个节点

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
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @param Integer $n
     * @return ListNode
     */
    function removeNthFromEnd($head, $n) {
        $slow = $fast = $head;
        while ($n>0) {
            $n--;
            $fast = $fast->next;
        }
        while($fast != null && $fast->next != null) {
            $fast = $fast->next;
            $slow = $slow->next;
        }
        if ($slow == $head && $fast == null) {
            return $head->next;
        }
        $slow->next = $slow->next->next;
        return $head;
    }
}

题目三

三数之和

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) {
        if (count($nums) < 3) {
            return [];
        }
        $res = [];
        sort($nums);
        $length = count($nums);
        
        for ($i = 0; $i < $length-2;$i++) {
            $start = $i+1;
            $end   = $length-1;
            if ($i>0&&$nums[$i]==$nums[$i-1]) {
                continue;
            }
            while ($start < $end) {
                if (($nums[$i] + $nums[$start] + $nums[$end]) == 0) {
                    $res[] = [$nums[$i], $nums[$start], $nums[$end]];
                    while($start<$end && $nums[$start] == $nums[$start+1]) {
                        $start++;
                    }
                    while($start<$end && $nums[$end] == $nums[$end-1]) {
                        $end--;
                    }
                    $start++;
                    $end--;
                } elseif (($nums[$i] + $nums[$start] + $nums[$end]) > 0) {
                    $end--;
                } else {
                    $start++;
                }
            } 
        }
        return $res;
    }

}