Mind palace

some thoughts

0%

Posted on Edited on In Disqus:
Symbols count in article: 562 Reading time ≈ 1 mins.

O(n)

1
2
3
4
5
6
7
8
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for x in nums:
            if x != val:
                nums[i] = x
                i += 1
        return i
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        for (int x : nums) {
            if (x != val) {
                nums[i++] = x;
            }
        }
        return i;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        for (int i = n - 1; i >= 0; --i) {
            if (nums[i] == val) {
                swap(nums[i], nums[--n]);
                nums.pop_back();
            }
        }
        return nums.size();
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

O(n) time

1
2
3
4
5
6
7
8
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for x in nums:
            if nums[i] != x:
                i += 1
                nums[i] = x
        return i + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (empty(nums)) return 0;
        int i = 0;
        for (int x : nums) {
            if (nums[i] != x) {
                nums[++i] = x;
            }
        }
        return i + 1;
    }
};

用这个

1
2
3
4
5
6
7
8
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for x in nums:
            if i < 1 or nums[i - 1] < x:
                nums[i] = x
                i += 1
        return i
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 0;
        for (int x : nums) {
            if (i < 1 || x > nums[i - 1]) {
                nums[i++] = x;
            }
        }
        return i;
    }
};

快慢指针解法O(n)
题解
快指针fast遍历整个数组，遇到和slow不相同的数，就把nums[fast]赋给slow的下一个，同时慢指针slow向前一步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        int last = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[last] != nums[i]) {
                nums[++last] = nums[i]; // 先加加再写就可以了
            }
        }
        return last + 1; // 因为last是下标，所以要返回last + 1才是个数
    }
};

朴素解法O(n)
在每个位置从当前位置开始向后找到第一个比当前位置之前一个数更大的数赋给当前位置，每次向后找的时候就从之前找到的那个更大的数的位置继续向后找即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        int i = 1, j = i;
        for (; i < n; ++i) {
            if (nums[i] <= nums[i - 1]) {
                do { ++j; } while (j < n && nums[j] <= nums[i - 1]);
                if (j < n) nums[i] = nums[j];
                else return i;
            }
        }
        return n;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        for (int i = 1, j = i; i < n; ++i) {
            for (; j < n; ++j) {
                if (nums[j] > nums[i - 1]) {
                    nums[i] = nums[j];
                    break;
                }
            }
            if (j == n) return i;
        }
        return n;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

recursive O(n)
这个更清楚

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        p = head
        for i in range(k):
            if not p:
                return head
            p = p.next
        curr, prev = head, self.reverseKGroup(p, k)
        for i in range(k):
            succ = curr.next
            curr.next = prev
            prev = curr
            curr = succ
        return prev
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto p = head;
        int i = 0;
        for (; i < k && p; ++i) {
            p = p->next;
        }
        if (i < k) return head;
        auto prev = reverseKGroup(p, k), curr = head;
        while (k-- > 0) {
            auto succ = curr->next;
            curr->next = prev;
            prev = curr;
            curr = succ;
        }
        return prev;
    }
};
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto p = head;
        int t = k; // 这里不能用k因为后边还得用
        while (t-- > 0 && p) {
            p = p->next;
        }
        if (t >= 0) return head; // 这里检查尾部较短的部分，必须统计t因为p为nullptr时也可能需要reverse，并且t == 0也是有可能的因为t最后还要--
        auto prev = reverseKGroup(p, k), curr = head; // 一个正常的翻转链表操作
        while (k-- > 0) {
            auto succ = curr->next;
            curr->next = prev;
            prev = curr;
            curr = succ;
        }
        return prev;
    }
};
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto p = head;
        int i = 0;
        for (; i < k && p; ++i, p = p->next);
        if (i < k) return head;
        auto prev = reverseKGroup(p, k), curr = head;
        for (int i = 0; i < k; ++i) {
            auto succ = curr->next;
            curr->next = prev;
            prev = curr;
            curr = succ;
        }
        return prev;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.6k Reading time ≈ 1 mins.

recursive O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        curr = head.next
        succ = self.swapPairs(curr.next)
        curr.next = head
        head.next = succ
        return curr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;
        auto next = head->next, ret = swapPairs(next->next);
        next->next = head;
        head->next = ret;
        return next;
    }
};

iterative O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(next=head)
        prev, curr = dummy, head
        while curr and curr.next:
            succ = curr.next
            curr.next = succ.next
            succ.next = prev.next
            prev.next = succ
            prev = curr
            curr = curr.next
        return dummy.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy_head(0), *prev = &dummy_head, *curr = head;
        dummy_head.next = curr;
        while (curr && curr->next) {
            auto succ = curr->next;
            curr->next = succ->next;
            succ->next = prev->next;
            prev->next = succ;
            prev = curr;
            curr = prev->next;
        }
        return dummy_head.next;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 3.4k Reading time ≈ 3 mins.

归并 两两inplace merge O(nlogk) k是lists数 n是所有node数 O(1) space

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists: return None
        def merge(a, b):
            tail = dummy = ListNode()
            while a and b:
                if a.val < b.val:
                    tail.next = a
                    a = a.next
                else:
                    tail.next = b
                    b = b.next
                tail = tail.next
            tail.next = a if a else b
            return dummy.next
        step, n = 1, len(lists)
        while step < n:
            for i in range(0, n, step << 1):
                if i + step >= n: break
                lists[i] = merge(lists[i], lists[i + step])
            step <<= 1
        return lists[0]
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        auto merge = [](auto a, auto b) {
            ListNode dummy_head(0), *tail = &dummy_head;
            while (a && b) {
                if (a->val < b->val) {
                    tail->next = a;
                    a = a->next;
                } else {
                    tail->next = b;
                    b = b->next;
                }
                tail = tail->next;
            }
            tail->next = a ? a : b;
            return dummy_head.next;
        };
        for (int n = lists.size(), step = 1; step < n; step <<= 1) {
            for (int i = 0; i + step < n; i += (step << 1)) {
                lists[i] = merge(lists[i], lists[i + step]);
            }
        }
        return lists[0];
    }
};
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        for (int n = lists.size(), step = 1; step < n; step <<= 1) {
            for (int i = 0; i + step < n; i += (step << 1)) {
                lists[i] = merge(lists[i], lists[i + step]);
            }
        }
        return lists[0];
    }

    ListNode *merge(ListNode *a, ListNode *b) {
        ListNode dummy_head(0), *tail = &dummy_head;
        while (a && b) {
            if (a->val < b->val) {
                tail->next = a;
                a = a->next;
            } else {
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        tail->next = a ? a : b;
        return dummy_head.next;
    }
};

external sort O(nlogk) n is the number of all nodes, k is the number of linked lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from queue import PriorityQueue
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
ListNode.__lt__ = lambda x, y: x.val < y.val # ListNode无法直接比较，用val替代也不行，必须重载__lt__
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put(l)
        tail = dummy = ListNode()
        while not q.empty():
            l = q.get()
            tail.next = l
            tail = l
            l = l.next
            if l:
                q.put(l)
        return dummy.next
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto cmp = [](const auto &a, const auto &b) { return a->val > b->val; };
        priority_queue<ListNode *, vector<ListNode *>, decltype(cmp)> q(cmp);
        for (auto l : lists) {
            if (l) {
                q.push(l);
            }
        }
        ListNode dummy_head(0), *tail = &dummy_head;
        while (!q.empty()) {
            auto l = q.top(); q.pop();
            tail->next = l;
            tail = l;
            l = l->next;
            if (l) {
                q.push(l);
            }
        }
        return dummy_head.next;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.9k Reading time ≈ 2 mins.

backtracking O(2n) time
思路是只要左括号比右括号多就是合法的！！！

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        def gen(s, l, r):
            if l < 0 or r < 0 or l > r: return
            if not l and not r:
                res.append(s) # 注意这里不能用res += s因为s是Iterable会逐个追加，想整体追加要用append
                return
            gen(s + '(', l - 1, r) # 这里底层内存需要进行字符串复制，但是没办法，Python字符串literal不能修改，也不提供StringBuilder
            gen(s + ')', l, r - 1)
        gen('', n, n)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string s;
        dfs(s, n, n);
        return res;
    }

    void dfs(string &s, int nl, int nr) {
        if (nl < 0 || nr < 0 || nl > nr) return;
        if (nl == 0 && nr == 0) {
            res.push_back(s);
            return;
        }
        dfs(s += '(', nl - 1, nr);
        s.pop_back();
        dfs(s += ')', nl, nr - 1);
        s.pop_back();
    }

    vector<string> res;
};
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
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        nl = nr = n;
        string s;
        dfs(s);
        return res;
    }

    void dfs(string &s) {
        if (nl == 0 && nr == 0) {
            res.push_back(s);
            return;
        }
        if (nl == 0) {
            --nr;
            dfs(s += ')');
            ++nr;
            s.pop_back();
        } else if (nl == nr) {
            --nl;
            dfs(s += '(');
            ++nl;
            s.pop_back();
        } else {
            --nl;
            dfs(s += '(');
            ++nl;
            s.pop_back();
            --nr;
            dfs(s += ')');
            ++nr;
            s.pop_back();
        }
    }

    int nl, nr;
    vector<string> res;
};

如果需要轴对称

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
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string s;
        this->n = n;
        dfs(s, n, n);
        return res;
    }

    void dfs(string &s, int nl, int nr) {
        if (nl < 0 || nr < 0 || nl > nr) return;
        if (nl + nr == n) {
            res.push_back(s);
            for (int i = n - 1; i >= 0; --i) {
                if (s[i] == '(') {
                    res.back() += ')';
                } else {
                    res.back() += '(';
                }
            }
            return;
        }
        dfs(s += '(', nl - 1, nr);
        s.pop_back();
        dfs(s += ')', nl, nr - 1);
        s.pop_back();
    }

    int n;
    vector<string> res;
};

Posted on Edited on In Disqus:
Symbols count in article: 1.4k Reading time ≈ 1 mins.

iterative O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        tail = dummy = ListNode()
        while l1 and l2:
            if l1.val < l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 if l1 else l2
        return dummy.next
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy_head(0), *p = &dummy_head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        p->next = l1 ? l1 : l2;
        return dummy_head.next;
    }
};

recusive O(m+n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

stack O(n) time O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
d = {')': '(', '}': '{', ']': '['}

class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        for c in s:
            if c in d:
                if not stk or d[c] != stk[-1]:
                    return False
                else:
                    stk.pop()
            else:
                stk += c # 注意这里c是一个字符所以可以用+=
        return not stk
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unordered_map<char, char> m = {{')', '('}, {'}', '{'}, {']', '['}};
class Solution {
public:
    bool isValid(string s) {
        string stk;
        for (char c : s) {
            if (m.count(c)) {
                if (!stk.empty() && stk.back() == m[c]) {
                    stk.pop_back();
                } else return false;
            } else {
                stk += c;
            }
        }
        return stk.empty();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, char> hm{{')', '('}, {'}', '{'}, {']', '['}};
        stack<char> stk;
        for (auto c : s) {
            if (hm.count(c)) {
                if (stk.empty() || stk.top() != hm[c]) return false;
                stk.pop();
            } else {
                stk.push(c);
            }
        }
        return stk.empty(); // 注意最后要判空
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 2.5k Reading time ≈ 2 mins.

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(next = head)
        slow, fast = dummy, head
        for _ in range(n):
            fast = fast.next
        while fast:
            slow, fast = slow.next, fast.next
        slow.next = slow.next.next
        return dummy.next
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy_head = 0;
        dummy_head.next = head;
        auto fast = head, slow = &dummy_head; // slow指向head的前一个，这样最后slow指向要删的node的前一个，方便删除，比如[1]删倒数第1
        while (n-- > 0) {
            fast = fast->next;
        }
        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return dummy_head.next;
    }
};

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy_head = 0;
        dummy_head.next = head;
        auto fast = head, slow = &dummy_head;
        while (fast) {
            fast = fast->next;
            if (--n < 0) {
                slow = slow->next;
            }
        }
        slow->next = slow->next->next;
        return dummy_head.next;
    }
};

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // write your code here
        ListNode dummy_head(0);
        dummy_head.next = head;
        ListNode *fast = head;
        while (n-- > 0 && fast) {
            fast = fast->next;
        }
        if (n >= 0) return head; // 要考虑链表长度不足n
        ListNode *slow = head, *prev = &dummy_head;
        while (fast) {
            prev = prev->next;
            slow = slow->next;
            fast = fast->next;
        }
        prev->next = slow->next;
        return dummy_head.next;
    }
};
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == nullptr)
            return head;
        auto front(head);
        auto behind(&head);
        while (front) {
            front = front->next;
            if (--n < 0)
                behind = &(*behind)->next;
        }
        auto to_be_deleted(*behind);
        *behind = (*behind)->next;
        delete to_be_deleted;
        return head;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1.7k Reading time ≈ 2 mins.

左右夹逼O(n3) time O(1) space
kSum的复杂度下界是O(nk-1)

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
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if not nums: return []
        nums.sort()
        n, res = len(nums), []
        # mx = nums[-1]
        for i in range(n):
            # if nums[i] + 3 * mx < target: continue
            # if 4 * nums[i] > target: break
            if i > 0 and nums[i - 1] == nums[i]: continue
            for j in range(i + 1, n):
                # if nums[i] + nums[j] + 2 * mx < target: continue
                # if nums[i] + 3 * nums[j] > target: break
                if j > i + 1 and nums[j - 1] == nums[j]: continue
                l, r, t = j + 1, n - 1, target - nums[i] - nums[j]
                while l < r:
                    s = nums[l] + nums[r]
                    if s == t:
                        res.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        while l < r and nums[l - 1] == nums[l]: l += 1
                        r -= 1
                        while l < r and nums[r] == nums[r + 1]: r -= 1
                    elif s < t:
                        l += 1
                        while l < r and nums[l - 1] == nums[l]: l += 1
                    else:
                        r -= 1
                        while l < r and nums[r] == nums[r + 1]: r -= 1
        return res
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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
        if (n < 4) return {};
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // 注意跳过重复的数
            for (int j = i + 1; j < n; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 注意跳过重复的数
                int l = j + 1, r = n - 1;
                int t = target - nums[i] - nums[j];
                while (l < r) {
                    int s = nums[l] + nums[r];
                    if (s < t) {
                        do { ++l; } while (l < r && nums[l] == nums[l - 1]);
                    } else if (s > t) {
                        do { --r; } while (l < r && nums[r] == nums[r + 1]);
                    } else {
                        res.push_back({nums[i], nums[j], nums[l], nums[r]});
                        do { ++l; } while (l < r && nums[l] == nums[l - 1]);
                        do { --r; } while (l < r && nums[r] == nums[r + 1]);
                    }
                }
            }
        }
        return res;
    }
};