3sum

这道题目和3sum closest差不多，都是用夹逼法可以做到，时间复杂度是max(O(n^log n), O(n^2)) 但是需要注意的是这道题目要求得到的结果不重复，不重复的结果需要用unique去掉重复的那些元素 unique是C++中用来除去容器中相同元素的函数，它的做法是将重复的元素用后面的元素进行覆盖，所以原来容器的大小是不变化的，在unique后面接一个erase就能够去掉重复元素了 其实用记录上一个结果的方式也能够去掉重复，代码如下 class Solution { public: vector > threeSum(vector &num) { vector> result; sort(num.begin(), num.end()); if (num.size() <= 2) return result; const int target = 0; int prev_a, prev_b, prev_c; for (auto a = num.begin(); a != prev(num.end(), 2); prev_a = *a, a++){ if (a != num.begin() && prev_a == *a) continue ; auto b = next(a); auto c = prev(num.end()); prev_b = *b + 1; prev_c = *c + 1; while (b < c){ int cur_sum = *a + *b + *c; if (cur_sum == target){ if (!(prev_b == *b && prev_c == *c)){ result.push_back({*a, *b, *c}); prev_b = *b, prev_c = *c; } b++, c--; continue ; } if (cur_sum > target) c--; else b++; } } //sort(result.begin(), result.end()); //result.erase(unique(result.begin(), result.end()), result.end()); return result; } };

[Leetcode]Longest Valid Parenthese

Longest Valid Parentheses Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4. 这道题只需要从左到右扫描一遍就可以，分为下面的情况 如果碰到的是(，则压栈，压入当前扫描的位置 如果碰到的是)，则 1. 如果栈为空，则说明到该位置并不符合条件，即左括号个数<右括号个数，且不存在某个中间位置i，使得从i到b是符合条件的，也就是能够从中间开始，因为如果存在这样的i，则a到i是符合条件的，i到b是符合条件的，也就是说a到b是符合条件的，所以这段结束了就可以记录一下b的位置，记为last 2. 如果栈不为空，则弹栈，还分下面两种情况 2.1 若此时栈为空，则max_len更新为max(i - last, max_len) 2.2 若此时栈不为空，则更新max_len为max(max_len, i - s.top())，s.top()到i的距离，也就是说在s.top()和i之间的是符合条件的没有问题

记录学习程序的过程

新开一个博客，用作技术博客，这个坑开了就要好好做下去。 现在研究生二年级，是个技术菜鸟，ACG方面略有涉猎，但忘性大，也不是很喜欢堕坑。希望能够成长为一个对计算机有扎实理解，database，compiler，server都有涉猎，以及借此锻炼元编程能力。研究生一年级就当是被狗吃了吧╮(╯▽╰)╭ 就像watashi说的那样，慢慢做就可以了。