【算法】字符串和数组操作01

1、无重复字符的最长子串

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

示例:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let arr = [], max = 0;
    for( let i = 0; i < s.length; i++ ) {
        let index = arr.indexOf(s[i]);
        if( index !== -1 ) {
            arr.splice( 0, index+1 );
        }
        arr.push( s.charAt(i) );
        max = Math.max(arr.length, max);
    }

    return max;
};

2、最长回文子串

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

思路：对于一个回文子串，例如cbabc，去掉首尾的c，它依旧是一个回文子串。因此我们可以通过P(i,j)表示从下标i到j是否是回文字符串，状态转移方程：P(i,j) = P(i+1,j-1)^(s[i]===s[j])。

示例：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let n = s.length;
    let res = '';
    let dp = Array.from( new Array(n),() => new Array(n).fill(0) );
    for( let i = n-1; i >= 0; i-- ) {
        for( let j = i; j < n; j++ ) {
            dp[i][j] = s[i] == s[j] && (j - i < 2 || dp[i+1][j-1]);
            if(dp[i][j] && j - i +1 > res.length){
                res = s.substring(i, j+1);
            }
        }
    }
    return res;
};

3、两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

思路：通过哈希表，将出现的元素以（key：数组，value：下标），当我们遍历每一个元素时，只需要判断target - nums[i]是否在哈希表存在值就可以。

示例：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var map = new Map();
    for(var i=0;i<nums.length;i++) {
        // 判断哈希表中是否存在相应target - nums[i]值。
        if(map.has(target - nums[i]) && map.get(target - nums[i]) !== i) {
            return [map.get(target - nums[i]), i];
        }
        map.set(nums[i], i);
    }
    return []
};