leetCode有兴趣的可以去看看，我们直接上干货啦= =
第一道题 - 难度（★）
输入一个数组跟一个目标值，当数组中某两个数之和等于目标值，返回这两个数的索引(下标)注意这两个数不能相同。(如果内部有多对符合要求的输出一对即可)
var twoSum = function(nums, target) {
for(let i = 0; i < nums.length; i ++) {
for(let k = i + 1; k < nums.length; k ++) {
if(nums[k] + nums[i] === target) {
return [i,k];
}
}
}
};
这个虽然简单，但是性能较差，能不能用O(n)的方式实现呢？怎么实现？
const handle = (nums, target) => {
let map;
for(let i = 0; i < nums.length; i ++) {
map = target - nums[i];
if(nums.indexOf(map) !== i && nums.includes(map)) {
return [i, nums.indexOf(map)]
}
}
}
var twoSum = function(nums, target) {
return handle(nums, target);
};
这种方式呢，虽说看似只有一个for循环，但indexOf，includes方法都是比较耗时的，因而也不建议用。从下图中也可以看出，该方法较第一种我们认为比较慢的方法还整整慢了接近4倍。
那它的思想是怎样的？假设要从[2,7,9,11]中找出两个数和为9，先把第一个的数据存入对象{2： 0}，这时候你思考下，目标值 - 数组每一项出来的是什么？如果说数组中的数据比如第2个是7，这个7，目标值 - 7是不是刚好是2？也就是说，如果这个对象里面有数值的和为9，那么目标值减去数组的每一项的这个值一定是对象中的某个key。对吧？
我们一起看看代码是怎样实现的吧。
const handle = (nums, target) => {
let map = {},
result = [];
for(let i = 0; i < nums.length; i ++) {
let firstNum = target - nums[i];
typeof map[firstNum] != "undefined" ? result.push(map[firstNum], i) : map[nums[i]] = i;
}
return result;
}
var twoSum = function(nums, target) {
return handle(nums, target);
};
而此时所花的时间呢？72ms，大大的提升了效率，对吧？
这种通过对象的key来快速定位的情况在算法中应用很广泛，因为你可能就直接少了一个维度的循环，对象怎么快速找到这个key的，你不用管，反正，是基于底层实现，类似于数据库或者es，查索引的方式是无比快速的。远比你写一个for循环快。
嗯好了，第一道题铺得有点开，后面简单点。
第二道题 - 难度(★★)
找出一个字符串中最长不重复片段，返回这个片段的长度。
var lengthOfLongestSubstring = function(s) {
let map = {},
current = 0,
max = 0;
for(let i = 0; i < s.length; i ++) {
current = map[s[i]] >= current ? map[s[i]] + 1 : current;
map[s[i]] = i;
max = max > i - current + 1 ? max : i- current + 1;
}
return max;
}
当然这里其实解法有很多种，但是这种方式是O(n)的方式，会比较快，性能较好。如果有更好的思路欢迎提出讨论。
第三题 - 难度(★★★)
输入两个数组，找出这两个数组所有数的中位数。注意时间复杂度应该为O(log(m + n))
那我们需要怎样的思路，来完成这个东西呢？
最简单的，不是查找中位数嘛，我合并这两个数组，给他们排序，再取最中间的那一个或两个对吧？是不是很简单？
说到排序，还记得我们之前说过的，各种排序吗？我们用个简单的快排来实现一下吧。（当然直接用sort方法也是好的）
const interchange = (arr, i, k) => [arr[i], arr[k]] = [arr[k], arr[i]];
const sort = (left, right, arr) => {
let i = left,
j = right,
reference = arr[left];
if(i >= j) return;
while(i < j) {
while(i < j && arr[j] >= reference) j --;
while(i < j && arr[i] <= reference) i ++;
arr[i] > arr[j] && interchange(arr, i, j);
}
interchange(arr, left, i);
sort(left, i - 1, arr);
sort(i + 1, right, arr);
}
var findMedianSortedArrays = function(nums1, nums2) {
let arr = nums1.concat(nums2),
len = arr.length;
sort(0, len - 1, arr);
return len%2 ? arr[Math.floor(len/2)] : (arr[len/2 - 1] + arr[len/2]) / 2;
};
这里个人觉得这种方法还是比较慢，有什么更好的方式多谢指教。
第四题 - 难度(★★)
找出一个字符串中最长的回文字符串。
首先肯定是写一个逻辑判断是否是字符串对吧？再写一个逻辑查找过程是吧？
这个其实也是一个水漫金山的过程：
那又怎么查找？回文的字符串可能是"aba"，也可能是"bb"，或者是"abba"，甚至就单单一个"a"，我的实现思路是这样：长度超过2的情况下，如果最终的结果的长度是奇数，那就是会有i - k 跟 i + k是一样的对吧？一定是的？对吧？如果长度是偶数呢？那一定会存在着最中间有偶数个数是一样的，对吧？比如"abba",“abccba”,“abbbba”，只要找到最中央这两个数，再还是按照第一种的方式一步步往外漫，比如设置一个k值，慢慢一步步加，只要两侧是相等的，就加1，这样是不是就能找到我们所有的回文字符串？再对比每一个回文字符串的长度，拿出最长的是不是就可以了？当然，要更快的话还是跟上面的一样，存的这个中间量(result)比原来的长就更新，不长就不管
看看代码是怎样的哈：
const palindromic = str => str.split("").reverse().join("") === str ? true : false;
const handle = s => {
let result = s[0];
for(let i = 0; i < s.length; i ++) {
if(s[i - 1] === s[i + 1]) {
let k = 2;
while(s[i - k] === s[i + k]) {
k ++;
}
result = result.length < (2 * k - 1) ? s.substr(i - (k - 1), 2 * k - 1) : result;
}
if(s[i] === s[i + 1]) {
let k = 1;
while(s[i - k] === s[i + 1 + k]) {
k ++;
}
result = result.length < 2 * k ? s.substr(i - (k - 1), 2 * k) : result;
}
}
return result;
}
var longestPalindrome = function(s) {
if(s === '' || s.length < 2 || palindromic(s)) return s;
return handle(s);
};
这种方式应该算是较好的了，从结果上看的话，性能超过97.69%的同语言算法。
好啦，leetCode我就抛砖引玉到这里啦。比较好的一种提高我们思维模式的一个途径了。想去瞧瞧的，可以看这里leetCode