【LeetCode】只出现一次的数字&&最长回文子串&&无重复字符的最长子串

只出现一次的数字

这是 136 题

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

解题思路

这是一道简单题，没有什么难点。虽然不难，但是可以用多种方法来解决它，接下来我就来介绍一下解决这题的多种思路。结果不重要，重要的是解题过程。

暴力法

拿到这题，首先能想到的一种思路就是暴力法。因为只有某一个元素出现过一次，所以在循环的过程中被记录到一次的数字就是我们需要找的那个元素。至于通过什么方式来循环，我们可以先将数组进行排序，这样只需要一次循环即可。整体思路如下：

• 首先将数组进行排序
• 然后对排序后的数组进行遍历循环，每次循环加二
• 如果前一个数和后一个数不相等，则说明该数只出现过一次，返回结果即可。

相关代码如下：

var singleNumber = function(nums) {
 nums.sort((a,b) => a - b);
    for(let i = 0; i < nums.length; i+=2){
        if(nums[i] !== nums[i+1]) return nums[i];
}
}

循环存储法

其实除了暴力法，哈希法也是大家很容易能想到的一种思路。但是这里不介绍哈希法，用另一种方法来代替哈希求解，因为我们需要在意解题的过程。对于循环存储，整体思路如下：

• 我们需要利用对象的属性来存储数组的元素
• 每次循环的时候去查找当前元素是否存在，如果存在就删掉
• 如果符合条件，最后只会剩下一个元素在对象里，这就是我们需要的结果
• 最后 for in 返回最后一个元素即可

相关代码如下：

var singleNumber = function(nums) {
  var result = {}
  for (var i = 0; i<nums.length; i++) {
    if (!result[nums[i]]) {
      result[nums[i]] = nums[i]
    } else {
      delete result[nums[i]]
    }
  }
  var res;
  for (i in result) {
    res = result[i]
  }
  return res
};

最长回文子串

这是力扣第 5 题

给你一个字符串  s，找到  s  中最长的回文子串。

解题思路

这是一道中等难度的题目，相对而言是有一点难度的。此题有很多比较高级的解法，比如动态规划。目前我们还没有讲到过动态规划，因为比较有难度，笔者我还正在研究，争取早日弄明白动态规划。因此在这里就不介绍类似于动态规划的解题思路了。在这里我将介绍几种比较常用且容易理解的方法，比如双指针法。

双指针法

碰到中等难度的题目，我们又和我们的老朋友双指针见面了（由此可见双指针多么重要，非常有用，大家一定要掌握）。

什么是回文串，回文串有两种，一种是长度为奇数的回文串（如 abcba，中心是 c），另一种是长度为偶数的回文串（如 abccba，中心是 cc），因此，我们就可以通过移动指针遍历数组，然后设置好临界条件来获取满足条件的情况。因为回文串有两种情况，所以我们需要分奇偶来遍历数组。完成后，通过 max 函数取出最大长度的回文字符串。

相关代码如下：

var longestPalindrome = function(s) {
    let max = ''
    for(let i=0; i< s.length; i++) {
        helper(i, i)
        helper(i, i+1)
    }
    function helper(l, r) {

        while(l>=0 && r< s.length && s[l] === s[r]) {
            l--
            r++
        }
       r+1-1
        const maxStr = s.slice(l + 1, r + 1 - 1);
        if (maxStr.length > max.length) max = maxStr
    }
    return max
};

暴力法

再来介绍一位老朋友 —— 暴力法。通俗点理解，我们直接对字符串暴力遍历也是可以求出结果的，但是时间复杂度太高了（O（n^3）时间复杂度）。不过实在想不出更好的方法，暴力是我们解题当中最后的倔强。暴力法就不用多解释了，直接 for 循环遍历即可。

相关代码如下：

var longestPalindrome = function(s) {
    let ans = '';
    let max = 0;
    let len = s.length
    for(var i = 0;i<len;i++){
        for(var r = i+1;r<=len;r++){
            let tmpStr = s.substring(i,r)
            if(isPalindrome(tmpStr) && tmpStr.length > max){
                ans = s.substring(i,r)
                max = tmpStr.length;
            }
        }
    }
    return ans;
}
function isPalindrome(str) {
    let len  = str.length
    let middle = parseInt(len/2)
    for(var i = 0;i<middle;i++){
        if(str[i]!=str[len-i-1]){
            return false
        }
    }
    return true
}

无重复字符的最长子串

这是力扣第 3 题

给定一个字符串  s ，请你找出其中不含有重复字符的  最长子串 的长度。

解题思路

这是一道中等难度的题目，算是很多人心中的回忆了吧（毕竟是力扣第三题，很多人的刷题记忆都是从这里开始的）。这题说难也不难，说简单也不简单。因为从通过率上来看，貌似不是很理想，但是从题意上看，感觉又不是很难。所以这题值得探讨一下。接下来将介绍一下以下几种解题思路。

双指针法

首先最容易想到的思路是双指针法，双指针法讲了这么多次，想必大家都很对它比较熟悉了吧。对于这题而言，创建两个 left 和 right 指针, 当让 right 指针前移的时候, 就去检测 max 的值；当让 left 指针前移的时候，就直接进入下一个循环。当两个指针相减大于 max 时，就返回此时的 max 值。

相关代码如下：

var lengthOfLongestSubstring = function(str) {
    if (str.length <= 1) {return str.length}
      let left = 0
      let right = 1
      let max = 0
      let temp
      while(right<str.length){
        temp = str.slice(left, right)
        if (temp.indexOf(str.charAt(right)) > -1) {
          left++
          continue
        } else {
          right++
        }
        if (right - left > max) { max = right - left }
      }
      return max
};

数组

字符串相关的题目用数组思想来解决也是常用的思路。用数组解决此题的思路是将没有重复的值按顺序放入到新数组 temp 中，当出现重复数字时，就以该数字后面的元素为起始头往下寻找。整体思路如下：

• 遍历数组，将数组中不重复的值去除
• 如果有重复值出现，去除第一个元素，将刚才重复的值重新导入数组
• 最后通过 Math 函数选出两个值中较大的那个值并返回最终结果

相关代码如下：

var lengthOfLongestSubstring = function(s) {
    let res = 0, temp = []
    for (let i=0;i<s.length;i++) {
        if (temp.indexOf(s[i]) == -1) {
            temp.push(s[i])
        } else {
            temp.shift()
            i--
            continue
        }
        res = Math.max(res, temp.length)
    }
    return res
};