# LeetCode Summary
:::spoiler Table of Contents
[TOC]
:::
## bebo1010 -- python
### Sorting
#### One Line Sorting
:::spoiler Sort by another Dictionary
```python
sorted(nums, key = lambda element: key_dict[element])
```
:::
:::spoiler Sort by Height
```python
[name for name, height in sorted(zip(names, heights), key=lambda item: item[1], reverse=True)]
```
:::
:::spoiler Sort by Most Profit
```python
difficulty, profit = zip(*sorted(zip(difficulty, profit), key=lambda i: i[1], reverse=True))
```
:::
:::spoiler Sort by Occurrences then Elements
[1636. Sort Array by Increasing Frequency](https://leetcode.com/problems/sort-array-by-increasing-frequency)
Sort by occurences in ascending order, then sort by elements themself in descending order
```python=
from collections import Counter
occurrences = Counter(nums) # a dict that stores occurrences, {element: occurrence}
sorted(nums, key=lambda element: (occurrences[element], -element))
```
:::
#### Radix Sort
[912. Sort an Array](https://leetcode.com/problems/sort-an-array)
:::spoiler 2-Based Radix Sort
```python=
def counting_sort(arr, exp, min_value):
n = len(arr)
output = [0] * n # Output array
count = [0] * 2 # Counting array for base 2 (0 and 1)
# Store count of occurrences in count[]
for i in range(n):
index = ((arr[i] - min_value) >> exp) & 1
count[index] += 1
# Change count[i] so that count[i] now contains actual
# position of this digit in output[]
count[1] += count[0]
# Build the output array
i = n - 1
while i >= 0:
index = ((arr[i] - min_value) >> exp) & 1
output[count[index] - 1] = arr[i]
count[index] -= 1
i -= 1
# Copy the output array to arr[], so that arr now
# contains sorted numbers according to current digit
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
# Find the minimum and maximum number to know the range
min_value = min(arr)
max_num = max(arr) - min_value
exp = 0
while (max_num >> exp) > 0:
counting_sort(arr, exp, min_value)
exp += 1
```
:::
### Graph
#### Dijkstra's Algorithm
[1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/)
[Dijkstra's Algorithm Reference](https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E5%9F%BA%E7%A4%8E%E6%BC%94%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97-graph-%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87dijkstras-algorithm-6134f62c1fc2)
:::spoiler Dijkstra's Algorithm for Directed Graph Implementation
```python=
def dijkstra_algorithm(n: int, starting_point: int, edges: List[List[int]]) -> list[int]:
visited = [False] * n
cost = [float('inf')] * n
prev_node = [-1] * n
cost[starting_point] = 0
current_point = starting_point
while not all(visited):
for edge in edges:
start, end, edge_cost = edge
if current_point == start and not visited[end]:
new_cost = cost[current_point] + edge_cost
if new_cost < cost[end]:
cost[end] = new_cost
prev_node[end] = start
visited[current_point] = True
min_cost = float('inf')
next_point = -1
for i in range(n):
if not visited[i] and cost[i] < min_cost:
min_cost = cost[i]
next_point = i
if next_point == -1:
break
current_point = next_point
return cost
```
:::
:::spoiler Dijkstra's Algorithm for Undirected Graph Implementation
```python=
def dijkstra_algorithm(n: int, starting_point: int, edges: List[List[int]]) -> list[int]:
visited = [False] * n
cost = [float('inf')] * n
prev_node = [-1] * n
cost[starting_point] = 0
current_point = starting_point
bidirectional_edges = edges + [[end, start, edge_cost] for start, end, edge_cost in edges]
while not all(visited):
for edge in bidirectional_edges:
start, end, edge_cost = edge
if current_point == start and not visited[end]:
new_cost = cost[current_point] + edge_cost
if new_cost < cost[end]:
cost[end] = new_cost
prev_node[end] = start
visited[current_point] = True
min_cost = float('inf')
next_point = -1
for i in range(n):
if not visited[i] and cost[i] < min_cost:
min_cost = cost[i]
next_point = i
if next_point == -1:
break
current_point = next_point
return cost
```
:::
### Tree
#### Character Trie
[648. Replace Words](https://leetcode.com/problems/replace-words)
:::spoiler Character Trie Implementation
Path of tree is represented by the character, initialize a node per path.
```python=
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str):
node = self.root
for char in word:
if node.is_end_of_word:
return
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search_shortest_prefix(self, word: str) -> str:
node = self.root
prefix = ""
for char in word:
if char not in node.children:
break
prefix += char
node = node.children[char]
if node.is_end_of_word:
return prefix
return word
```
:::
#### Depth First Search
[1038. Binary Search Tree to Greater Sum Tree](https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree)
:::spoiler Reverse In-order Depth First Search Implementation
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def right_first_dfs(self, current_node: TreeNode):
if current_node is None:
return
self.right_first_dfs(current_node.right)
self.current_sum += current_node.val
current_node.val = self.current_sum
self.right_first_dfs(current_node.left)
```
:::
[1110. Delete Nodes And Return Forest](https://leetcode.com/problems/delete-nodes-and-return-forest)
:::spoiler Post-order Depth First Search Implementation
```python=
def depth_first_post_order(self, root: TreeNode, delete_flag: bool):
if root is None:
return None
if root.val in self.to_delete_set:
to_be_deleted = True
else:
to_be_deleted = False
root.left = self.depth_first_post_order(root.left, to_be_deleted)
root.right = self.depth_first_post_order(root.right, to_be_deleted)
if not to_be_deleted and delete_flag:
self.root_list.append(root)
if to_be_deleted:
return None
else:
return root
```
:::
[1382. Balance a Binary Search Tree](https://leetcode.com/problems/balance-a-binary-search-tree)
:::spoiler In-order Depth First Travesal Implementation
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def in_order_traversal(self, current_node: TreeNode):
if current_node == None:
return None
self.in_order_traversal(current_node.left)
self.values.append(current_node.val)
self.in_order_traversal(current_node.right)
```
:::
:::spoiler Build Balanced Binary Search Tree from Array Implementation
```python=
def build_balanced_BST(self, values: list) -> TreeNode:
if len(values) == 0:
return None
mid_point = int(len(values) >> 1)
root = TreeNode(values[mid_point])
root.left = self.build_balanced_BST(values[:mid_point])
root.right = self.build_balanced_BST(values[mid_point+1:])
return root
```
:::
### Stack
#### Find Score by Removing Substring
[1717. Maximum Score From Removing Substrings](https://leetcode.com/problems/maximum-score-from-removing-substrings)
:::spoiler Remove Substring using Stack Implementation
```python=
def find_ab_scores(self, s: str, score: int) -> [str, int]:
partial_score = 0
stack = []
for c in s:
if c != 'b':
stack.append(c)
else:
if len(stack) > 0:
if stack[-1] == 'a':
print("added x")
partial_score += score
stack.pop()
else:
stack.append(c)
else:
stack.append(c)
# stack.reverse()
return "".join(stack), partial_score
```
:::
### Heap Queue
[703. Kth Largest Element in a Stream](https://leetcode.com/problems/kth-largest-element-in-a-stream)
[Python Heap Queue Algorithm Document](https://docs.python.org/3/library/heapq.html)
:::spoiler Heap Queue Details
Initialize the heap with a empty list `x = []` or convert a list with `heapq.heapify(x)`
`heap[0]` is the smallest item in the heap.
- `heapq.heappush(heap, item)`
Push the value `item` onto the heap
- `heapq.heappop(heap)`
Pop the smallest `item` from the heap
If the `heap` is empty, `IndexError` is raised
To access the smallest `item` without popping it, use `heap[0]`
- `heapq.heappushpop(heap, item)`
Push the value `item` onto the heap, then pop and return the smallest `item` from the heap
More efficient than `heapq.heappush()` then `heapq.heappop()`
- `heapq.heapreplace(heap, item)`
Pop and return the smallest `item` from the heap, then push the value `item` onto the heap
If the `heap` is empty, `IndexError` is raised
More efficient than `heapq.heappop()` then `heapq.heappush()`
Heap elements can also be tuples.
```python
>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')
```
:::
::: spoiler Example for Heap Sort
```python=
def heapsort(iterable):
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
```
:::
### Miscellany
#### Pascal Triangle
[118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle)
:::spoiler Pascal Triangle Implementation
```python=
def generate(numRows: int) -> List[List[int]]:
full_triangle = [[1]] # base case
for row in range(2, numRows + 1):
prev_row = full_triangle[row - 2]
current_row = []
middle_point = row >> 1
element = 1
for index in range(middle_point):
if index == 0:
current_row.insert(0, 1)
current_row.insert(-1, 1)
else:
element = prev_row[index - 1] + prev_row[index]
current_row.insert(index, element)
current_row.insert(-index, element)
if row & 0x01 == 1:
element = prev_row[middle_point - 1] + prev_row[middle_point]
current_row.insert(middle_point, element)
full_triangle.append(current_row)
return full_triangle
```
:::
#### Modulo Sums
[523. Continuous Subarray Sum](https://leetcode.com/problems/continuous-subarray-sum)
:::spoiler Modulo Sums Explanation
The sum of any array can be rewritten as follow:
$\text{sum}(:j) = \text{sum}(:i) + \text{sum}(i:j)$ for all $i < j$
For a subarray with size greater than 1 to exist such that the sum of its elements is `divisivble by k`, $\text{sum}(i:j) \% k$ must equal to 0 for some $i < j - 1$, the reason for $j - 1$ is because the length of subarray must be greater than or equal to 2
If we modules both sides of the above equation:
$\text{sum}(:j) \% k = [\text{sum}(:i) + \text{sum}(i:j)] \% k$
$\Rightarrow \text{sum}(:j) \% k = [\text{sum}(:i) \%k + \text{sum}(i:j) \%k] \% k$
$\Rightarrow \text{sum}(:j) \% k = \text{sum}(:i) \%k$
Find the $i$ and $j$ that satisfy this condition
:::
#### Sliding Window
[2134. Minimum Swaps to Group All 1's Together II](https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii)
:::spoiler Techniques for using Sliding Window on Circular Array
Assume the window size is `sliding_window_size`.
1. Use modulation to calculate index, quite slow
```python=
nums = [1, 2, 3]
sliding_window_size = 2
for i in range(0, len(appended_nums) - k + 1):
subarray = [nums[(i + j) % len(nums)] for j in range(sliding_window_size)]
...
```
2. Append the first `k` elements to the end of array, faster
```python=
nums = [1, 2, 3]
sliding_window_size = 2
appended_nums = nums + nums[:sliding_window_size]
for i in range(0, len(appended_nums) - sliding_window_size + 1):
subarray = appended_nums[i:i + sliding_window_size]
...
```
:::
#### Split String into Chunks
[273. Integer to English Words](https://leetcode.com/problems/integer-to-english-words)
Split the numbers from least significant digits into chunks
:::spoiler Spliting Implementation
```pyhton=
def split_into_chunks(number, chunk_size=3):
str_number = str(number)[::-1]
chunks = [str_number[i:i+chunk_size] for i in range(0, len(str_number), chunk_size)]
chunks = [chunk[::-1] for chunk in chunks]
return chunks
```
:::
#### Factorization
[650. 2 Keys Keyboard](https://leetcode.com/problems/2-keys-keyboard/description)
:::danger
How can this problem be reduced into a factorization problem?
:::
:::spoiler Factorization Implementation
The first part check if `n` is 1 (special case).
The second part check the multiple of 2.
The third part check other prime factors.
The last part is when the remaining of `n` is a prime factor, add it to the list.
```pyhton=
def get_prime_factors(n: int) -> list:
if n == 1:
return [1]
factors = []
while n % 2 == 0:
factors.append(2)
n //= 2
for i in range(3, int(n**0.5) + 1, 2):
while n % i == 0:
factors.append(i)
n //= i
if n > 2:
factors.append(n)
return factors
```
:::
:::spoiler Leetcode Editorial
```python=
class Solution:
def minSteps(self, n: int) -> int:
if n == 1:
return 0
self.n = n
self.memo = [[0] * (n // 2 + 1) for _ in range(n + 1)]
return 1 + self._min_steps_helper(1, 1)
def _min_steps_helper(self, curr_len: int, paste_len: int) -> int:
if curr_len == self.n:
return 0
if curr_len > self.n:
return 1000
# return result if it has been calculated already
if self.memo[curr_len][paste_len] != 0:
return self.memo[curr_len][paste_len]
opt1 = 1 + self._min_steps_helper(curr_len + paste_len, paste_len)
opt2 = 2 + self._min_steps_helper(curr_len * 2, curr_len)
self.memo[curr_len][paste_len] = min(opt1, opt2)
return self.memo[curr_len][paste_len]
```
:::
#### Bit-Wise Complement
[476. Number Complement](https://leetcode.com/problems/number-complement)
:::spoiler Bit-by-Bit Complement
1. Get the binary representation (in `str`) of original number `num` by `bin()`.
2. Complement the bits.
The return value of `bin()` would contain `0b` in them.
For example `bin(5)` returns `0b101`
$O(n)$ solution where $n$ is the number of bits used to represent the number
```python=
def findComplement(self, num: int) -> int:
new_str = "0b"
binary_string = bin(num)
for bit_index in range(2, len(binary_string)):
bit = binary_string[bit_index]
new_str += "0" if bit == "1" else "1"
return int(new_str, 2)
```
:::
:::spoiler Complement with Exclusive OR
1. Get the bit length of original number `num` by `bit_length()`.
2. Generate the mask.
3. Complement the number with the mask and XOR operation.
The return value of `bit_length()` is the number of bits used to represent the number.
For example `bin(5)` returns `3` (`0b101` takes 3 bits to represent).
$O(log(n))$ solution where $n$ is the number of bits used to represent the number
```python=
def findComplement(self, num: int) -> int:
bit_length = num.bit_length()
mask = (1 << bit_length) - 1
return num ^ mask
```
:::
#### Greatest Common Divisor
[2807. Insert Greatest Common Divisors in Linked List](https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list)
[Euclidean Algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm)
:::spoiler Find GCD with Euclidean Algorithm Implementation
```python=
def gcd(a, b):
while b:
a, b = b, a % b
return a
```
:::
## bebo1010 -- C++
### Circular Deque
[641. Design Circular Deque](https://leetcode.com/problems/design-circular-deque)
:::spoiler Circular Deque Implementation
`start_index` and `end_index` are the indices that's ready for the next insertion.
Thus having to recalculate index again when trying to `getFront()` and `getRear()`.
```c++=
class MyCircularDeque {
public:
MyCircularDeque(int k) : max_length(k){
deque.resize(k, -1);
}
bool insertFront(int value) {
if(deque_length == max_length){
return false;
}
deque[start_index] = value;
start_index = (start_index - 1 + max_length) % max_length;
deque_length++;
return true;
}
bool insertLast(int value) {
if(deque_length == max_length){
return false;
}
deque[end_index] = value;
end_index = (end_index + 1) % max_length;
deque_length++;
return true;
}
bool deleteFront() {
if(deque_length == 0){
return false;
}
start_index = (start_index + 1) % max_length;
deque[start_index] = -1;
deque_length--;
return true;
}
bool deleteLast() {
if(deque_length == 0){
return false;
}
end_index = (end_index - 1 + max_length) % max_length;
deque[end_index] = -1;
deque_length--;
return true;
}
int getFront() {
if(deque_length == 0){
return -1;
}
int front_index = (start_index + 1) % max_length;
return deque[front_index];
}
int getRear() {
if(deque_length == 0){
return -1;
}
int rear_index = (end_index - 1 + max_length) % max_length;
return deque[rear_index];
}
bool isEmpty() {
return deque_length == 0;
}
bool isFull() {
return deque_length == max_length;
}
private:
vector<int> deque;
const int max_length;
int deque_length = 0;
int start_index = 0;
int end_index = 1;
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/
```
:::
## bebo1010 -- C
### Array
#### Binary Search
[1331. Rank Transform of an Array](https://leetcode.com/problems/rank-transform-of-an-array)
Using basic `Linear Search` would trigger TLE at this question.
Use Binary Search instead.
:::spoiler Binary Search Implementation
```c=
int binary_search(int element, int *array, int array_length){
int left_index = 0;
int right_index = array_length;
int middle_index;
while(left_index < right_index){
middle_index = left_index + (right_index - left_index) / 2;
if(element == array[middle_index]){
return middle_index;
}
else if(element > array[middle_index]){
left_index = middle_index;
}
else{
right_index = middle_index;
}
}
return -1;
}
```
:::
### Bit-wise Operation
#### Remove first set bit from least significant bit
```c=
x = x & (x - 1);
```
This can be used to get how many set bits are in a number, for example:
```c=
count = 0;
while(x > 0){
count++;
x = x & (x - 1);
}
```
## sushake -- c
### String
#### string to array
```c=
char array1[] = source;
char* array2 = target;
//find length
int length = strlen(source);
```
### Graph
#### Dijkstra's Algorithm
[1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/)
- [Dijkstra's Algorithm Reference](https://medium.com/%E6%8A%80%E8%A1%93%E7%AD%86%E8%A8%98/%E5%9F%BA%E7%A4%8E%E6%BC%94%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97-graph-%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E8%88%87dijkstras-algorithm-6134f62c1fc2)
:::spoiler Dijkstra's Algorithm for Undirected Graph Implementation
```c=
int dijkstra(int** table, int start, int n) {
int* distance = (int*)malloc(sizeof(int) * n);
for(int i = 0; i < n; i++)
distance[i] = stable[start][i];
int* book = (int*)malloc(sizeof(int) * n);
memset(book, 0, sizeof(int) * n);
book[city] = 1;
for(int i = 0; i < n; i++) {
int min = INT_MAX;
int id = -1;
for(int j = 0; j < n; j++) {
if(book[j] == 0 && distance[j] < min) {
min = distance[j];
id = j;
}
}
if (id == -1)
break;
book[id] = 1;
for(int j = 0; j < n; j++) {
if(book[j] == 0 && table[id][j] != INT_MAX && distance[j] > distance[id] + road[id][j])
distance[j] = distance[id] + road[id][j];
}
}
}
```
:::
- [2976. Minimum Cost to Convert String I](https://leetcode.com/problems/minimum-cost-to-convert-string-i/description/?envType=daily-question&envId=2024-07-27)
這題會有時間限制,我的策略為將所有 distance 儲存在 26*26 表格裡，這樣就不會有重複找的問題。**這題有個噁心點: 他給的 cost 有重複的，需判斷哪個比較小。**
### Sort
#### quicksort
:::spoiler quicksort in C library
```c=
/* The comparison function must return an integer less than,
* equal to, or greater than zero if the first argument is
* considered to be respectively less than, equal to, or greater
* than the second. If two members compare as equal, their
* order in the sorted array is undefined. */
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int cmpstring(const void *p1, const void *p2)
{
/* The actual arguments to this function are "pointers to
pointers to char", but strcmp(3) arguments are "pointers
to char", hence the following cast plus dereference */
return strcmp(* (char * const *) p1, * (char * const *) p2);
}
qsort(array, arraySize, sizeof(int), cmpfunc);
```
:::
### Top Interview 150
#### Array / String
- [88. Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150)
因為答案會儲存在 array1 當中，所以節省記憶體空間的方法為從尾端開始填數字。
- [26. Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150)
:::spoiler [In-place algorithm](https://www.geeksforgeeks.org/in-place-algorithm/)
```c=
int removeDuplicates(int* nums, int numsSize) {
int i = 0;
int j = 0;
while(i < numsSize) {
int val = nums[i];
j +=1;
while(j < numsSize && nums[j] == val) {
j += 1;
}
i +=1;
if(j < numsSize)
nums[i] = nums[j];
else
break;
}
return i;
}
```
:::
- [55. Jump Game](https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150)
這題我是參照他人的[解法](https://leetcode.com/problems/jump-game/solutions/4534808/super-simple-intuitive-8-line-python-solution-beats-99-92-of-users/?envType=study-plan-v2&envId=top-interview-150)
- [12. Integer to Roman](https://leetcode.com/problems/integer-to-roman/description/?envType=study-plan-v2&envId=top-interview-150)
這題本來很笨的用 if 迴圈慢慢把 string 找出來，chatGPT 最後整理的程式碼，供參。順便紀錄怎麼增加 string 元素(strcat)。
:::spoiler string add item
```c=
char* intToRoman(int num) {
const char* roman_numerals[] = {
"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
const int values[] = {
1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
char* output = (char*)malloc(20);
output[0] = '\0';
int i = 0;
while (num > 0) {
while (num >= values[i]) {
strcat(output, roman_numerals[i]);
num -= values[i];
}
i++;
}
return output;
}
```
:::
- [14. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/description/?envType=study-plan-v2&envId=top-interview-150)
紀錄如何使用 strcpy 以及 strncpy ，詳細可參考這篇[文章](https://blog.csdn.net/weixin_37800531/article/details/141947145)講述差異性
:::spoiler string copy item
```c=
char* longestCommonPrefix(char** strs, int strsSize) {
if(strsSize == 0)
return "";
char* output = strs[0];
int length = strlen(output);
for(int i = 1; i < strsSize; i++){
char* word = strs[i];
int len = strlen(word);
for(int j = 0; j < length; j++){
if(len == 0 || output[j] != word[j]){
length = j;
break;
}
len--;
}
if(length == 0)
return "";
}
char* final = (char*)malloc(sizeof(char) * (length + 1));
strncpy(final, output, length);
final[length] = '\0'; //這個要自己加!!!
return final;
}
```
:::
#### Two Pointers
- [15. 3Sum](https://leetcode.com/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150)
**這題很重要，要會!!!**
這題我是看解答的，思路如下。
先從小到大排列，第一個迴圈用來固定第一個變數，這樣就是 2sum 的題目。
再來將第二個變數設為第一個變數位置加一，第三個變數位置設為佇列尾端，然後將三數相加跟零做比較 :
比零大表示第三個變數太大，往左移；比零小表示第二個變數太小，往右移。
:::spoiler 學起來如何使用 qsort
```c=
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
*returnSize = 0;
int** output = (int**)malloc(sizeof(int*) * (numsSize * numsSize));
for(int i = 0; i < numsSize - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;//skip duplicate
int second = i + 1;
int third = numsSize - 1;
while(second < third) {
int count = nums[i] + nums[second] + nums[third];
if(count == 0) {
output[*returnSize] = (int*)malloc(sizeof(int) * 3);
output[*returnSize][0] = nums[i];
output[*returnSize][1] = nums[second];
output[*returnSize][2] = nums[third];
(*returnSize) += 1;
// Skip duplicate 'left' and 'right' values
while (second < third && nums[second] == nums[second + 1]) second++;
while (second < third && nums[third] == nums[third - 1]) third--;
second++;
third--;
}else if(count > 0)
third --;
else
second++;
}
}
*returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
for (int i = 0; i < *returnSize; i++) {
(*returnColumnSizes)[i] = 3;
}
return output;
}
```
:::
- [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150)
這題有個重點，s consists of English letters, digits, symbols and spaces.
所以標點符號跟空白都需要包含。根據 ASCII 可顯示字元編號範圍是32-126（0x20-0x7E），共95個字元。
Sign in with Wallet
Connect another wallet