问题提出

#15 3Sum

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

buggy code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
#include <string>
#include <string.h>
using std::string;

int main() {
	string str = "abc";
	char *s = (char *)malloc(str.size());
	memcpy(s, str.data(), str.size());
	for (int i = 0; i < 4096*8; ++i) {
		printf("(%p,%c)", s + i, s[i]);
	}
	free(s);
	return 0;

}

问题提出

#11 盛最多水的容器

给定 n 个非负整数 a₁，a₂，…，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

问题提出

#5 Longest Palindromic Substring

如何快速找出一个字符串的最长回文子串？

问题提出

#4 Median of Two Sorted Arrays

如何在对数时间复杂度内找出两个有序数组的中位数？

问题提出

#480 Sliding Window Median

如何在尽可能少的时间内找出一个数组的中位数？简单粗暴的做法是先排序，再按照次序选择相应的数据。这种算法的时间复杂度主要依赖于排序算法的复杂度，快排可以将其降到O(nlog(n))。

本文介绍一种时间复杂度为O(n)的算法。

主要思路

思路是寻找第n大的元素，在一个序列中确定第一个元素的位置，将其置于正确的位置（即它左边的元素都小于它，右边的元素都大于它）。假设这个位置是k，如果k=n，很幸运，已经找到了，算法结束；如果k<n，则递归的在左边寻找；如果k>n，则递归的在右边寻找。