3. 無(wú)重復(fù)字符的最長(zhǎng)子串

給定一個(gè)字符串，找出不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。
示例：
給定 "abcabcbb" ，沒有重復(fù)字符的最長(zhǎng)子串是 "abc" ，那么長(zhǎng)度就是3。
給定 "bbbbb" ，最長(zhǎng)的子串就是 "b" ，長(zhǎng)度是1。
給定 "pwwkew" ，最長(zhǎng)子串是 "wke" ，長(zhǎng)度是3。請(qǐng)注意答案必須是一個(gè)子串，"pwke" 是 子序列 而不是子串。

分析思路：

1. 暴力法：取出所有的子串，校驗(yàn)沒有重復(fù)的最大值，顯然這種算法是有很多重復(fù)操作的。比如遍歷abc的時(shí)候已經(jīng)知道abc沒有重復(fù)，后面沒必要再進(jìn)行這段的比對(duì)。
2. 使用滑動(dòng)窗口，初始窗口左值為0，右值為1，右值開始遍歷字符串每個(gè)字符的同時(shí)，存入hash表，如果hash表中已經(jīng)有了改字符的索引，那么久移動(dòng)窗口的左值為該位置的下一個(gè)位置，繼續(xù)滑動(dòng)窗口，直到遍歷完字符串，思路并不算復(fù)雜。時(shí)間復(fù)雜度和空間復(fù)雜度都是O(n)

代碼如下:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()) {
            return 0;
        }
        int left = 0,right =1, string_length = s.size(),max_length = 0;
        unordered_map<char, int> hashMap;
        hashMap[s[left]] = left;
        max_length = 1;
        while (right < string_length) {
            auto it = hashMap.find(s[right]);
            if (it == hashMap.end()) {
                //沒有重復(fù)
                hashMap[s[right]] = right;
            }
            else{
                //有重復(fù)
                //更改滑動(dòng)窗口的左值為重復(fù)值的索引+1，先判斷下重復(fù)值是不是再當(dāng)前l(fā)eft的右邊
                left = max(left, it->second+1);
                hashMap[s[right]] = right;
            }
            
            max_length = max(max_length,right -left+1);
            right++;
        }
        return max_length;
    }
};

4. 兩個(gè)排序數(shù)組的中位數(shù)

給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2 。
請(qǐng)找出這兩個(gè)有序數(shù)組的中位數(shù)。要求算法的時(shí)間復(fù)雜度為 O(log (m+n)) 。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位數(shù)是 (2 + 3)/2 = 2.5

分析核心思路，中位數(shù)的數(shù)學(xué)定義就是該位置左邊的數(shù)和右邊的數(shù)數(shù)量一致。我們抽象s1數(shù)組存在位置i，s2的數(shù)組存在位置j，s1的數(shù)組i左邊的數(shù)加上s2數(shù)組j左邊的數(shù)正好是兩個(gè)數(shù)組總長(zhǎng)度的一半。這樣i和j就存在數(shù)學(xué)關(guān)系i+j= （m+n）/2。我們同時(shí)假設(shè)n是大于等于m的。這樣我們?cè)賡1數(shù)組中搜索位置i，j的位置根據(jù)數(shù)學(xué)關(guān)系也是對(duì)應(yīng)的，采用二分法搜索合適i的位置保證時(shí)間復(fù)雜度要求到O(log (m+n))

代碼如下

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(),n = nums2.size();
        //先確保m<=n 如果不是先交換一次指針
        if (m>n) {
            // 因?yàn)槭荂++引用，這里交換一下使用兩個(gè)臨時(shí)變量
            vector<int> tem1 = nums1;
            vector<int> tem2 = nums2;
            nums2 = tem1;
            nums1 = tem2;
            int tmpValue = m; m = n; n = tmpValue;
        }
        
        //先確定好i的值和中值
        int iMin = 0,iMax = m,halfLen = (m+n+1)/2;
        
        //開始遍歷
        while (iMin <= iMax) {
            //給定中值
            int i = (iMin + iMax) / 2;
            int j = halfLen -i;  //對(duì)應(yīng)關(guān)系 因?yàn)閕 + j = (m+n+1)/2;
            if (i < iMax && nums2[j-1]>nums1[i] ) {
                //i的值太小了，要加大i區(qū)間
                iMin = iMin+1;
            }
            else if (i > iMin && nums1[i-1] >nums2[j]){
                //i的值太大了，減少i區(qū)間
                iMax = iMax-1;
            }
            else{
                //完美匹配
                int maxLeft = 0;
                //邊界值判斷
                if (i == 0) {
                    maxLeft = nums2[j-1];
                }
                else if(j == 0){
                    maxLeft = nums1[i-1];
                }
                else{
                    maxLeft = max(nums1[i-1], nums2[j-1]);
                }
                //奇數(shù)直接return左邊邊界值
                if ( (m + n) % 2 == 1 ) { return maxLeft; }
                int minRight = 0;
                if (i == m) {
                    minRight = nums2[j];
                }
                else if (j == n){
                    minRight = nums1[i];
                }
                else {
                    minRight = min(nums2[j], nums1[i]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0f;
    }
};