再來聊聊數(shù)組

• 這篇我們來總結(jié)一下數(shù)組相關(guān)的一些算法，數(shù)組的特點(diǎn)在于我們能通過下標(biāo)得到對應(yīng)數(shù)據(jù)，時(shí)間復(fù)雜度在O(1)，之前有多篇文章有數(shù)組相關(guān)的體系，一下來一個(gè)歸納：

數(shù)據(jù)結(jié)構(gòu)與算法–判斷撲克牌是否順子

數(shù)據(jù)結(jié)構(gòu)與算法–翻轉(zhuǎn)單詞順序

數(shù)據(jù)結(jié)構(gòu)與算法–有序數(shù)組中找出和為s的兩個(gè)數(shù)字

數(shù)據(jù)結(jié)構(gòu)與算法–第一個(gè)只出現(xiàn)一次的字符

數(shù)據(jù)結(jié)構(gòu)與算法–數(shù)組中出一次的數(shù)字

數(shù)據(jù)結(jié)構(gòu)與算法–數(shù)字在排序數(shù)組中出現(xiàn)次數(shù)

數(shù)據(jù)結(jié)構(gòu)與算法–數(shù)組中的逆序?qū)?/p>

數(shù)據(jù)結(jié)構(gòu)與算法–將數(shù)組排成最小的數(shù)

數(shù)據(jù)結(jié)構(gòu)與算法-- 數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字（時(shí)間復(fù)雜度的討論）

數(shù)據(jù)結(jié)構(gòu)與算法–數(shù)組：二維數(shù)組中查找

數(shù)據(jù)結(jié)構(gòu)與算法–字符串的排列組合問題

數(shù)據(jù)結(jié)構(gòu)與算法–回朔，矩陣中查找字符串路徑

數(shù)據(jù)結(jié)構(gòu)與算法–字符串：字符串替換

數(shù)據(jù)結(jié)構(gòu)與算法–查找與排序另類用法

數(shù)據(jù)結(jié)構(gòu)與算法–經(jīng)典10大排序算法（動圖演示）【建議收藏】

• 以上是現(xiàn)階段已經(jīng)解除的數(shù)組相關(guān)，包括字符串其實(shí)也就是數(shù)組問題，其中用的最多的是雙指針，還有就是歸并法，二分法，其中排序是最重要的，在最后一排10大排序算法中詳細(xì)介紹了每一種排序，并有動圖演示。有的根據(jù)數(shù)組中數(shù)據(jù)的特殊性進(jìn)行解題，例如出現(xiàn)一次的數(shù)字，利用位運(yùn)算相關(guān)知識，還有排序算法思想的另類用法，利用排序思想進(jìn)行查詢。等，發(fā)現(xiàn)還是基礎(chǔ)知識的運(yùn)用最重要。
• 以上文章中都與是運(yùn)用數(shù)組進(jìn)行解題，或者是其中有一個(gè)方法是用的數(shù)組。
• 接下來是今天的題目：

最長子串問題：給定一個(gè)字符串，找出字符串中的最長子串，使得這個(gè)子串中沒有重復(fù)的數(shù)字

• 因?yàn)閷戇^之前的題目：有序數(shù)組中找出和為s的兩個(gè)數(shù)字 ，我第一反應(yīng)就是雙指針遍歷數(shù)組，分析如下：
  • 指針start，end都從0，開始，在end < length-1 情況下讓end++
  • 判斷當(dāng)前指針范圍內(nèi)是否有重復(fù)數(shù)字，
  • 如果有，當(dāng)前最長子串就是 maxTemp = start ~ end-1，先判斷最長子串與當(dāng)前maxTemp大小，取最大值，此時(shí)我們將start++
  • 如果沒有重復(fù)數(shù)字，那么我們繼續(xù)end++
  • 繼續(xù)如上步驟，知道end = length-1 或者start > end
• 以上遍歷一次能得到最終值，但是在判斷當(dāng)前范圍是否重復(fù)時(shí)候必然有額外開銷，
  • 如果直接遍歷判斷，那么最終時(shí)間復(fù)雜度將會變成O(n²)
  • 我用空間換時(shí)間
    • 如果輸入數(shù)據(jù)只有普通字符a~z，那么我們自建一個(gè)256 大小的hash表，用數(shù)組做容器
    • 如果輸入數(shù)據(jù)中海油漢字等其他字符，那么我們只能用Map集合了，或者用鏈表自實(shí)現(xiàn)Map，在上文 數(shù)據(jù)結(jié)構(gòu)與算法–第一個(gè)只出現(xiàn)一次的字符 我們就是如此實(shí)現(xiàn)
• 如下動圖：

• 如上分析有如下代碼：

/*** 給定一個(gè)字符串，找出字符串中的最長子串，使得這個(gè)子串中沒有重復(fù)的數(shù)字* @author liaojiamin* @Date:Created in 16:39 2021/7/15*/ public class FindLongestSubStr {public static void main(String[] args) {String maxSubStr = "1234578123";System.out.println(findLongestStr(maxSubStr));}/*** 雙指針實(shí)現(xiàn)滑動窗口，并空間換時(shí)間* */public static Integer findLongestStr(String str){if(str == null || str.length() <= 0){return 0;}Map<Character, Integer> validateMap = new HashMap<>();char[] chars = str.toCharArray();int positionStart = 0;int positionEnd = 0;int maxSumLength = 0;while (positionEnd <= chars.length -1 && positionStart <= positionEnd){if(validateMap.containsKey(chars[positionEnd])){validateMap.remove(chars[positionStart]);positionStart++;}else {validateMap.put(chars[positionEnd], 1);positionEnd++;}int length = positionEnd-1 - positionStart +1;if(maxSumLength < length){maxSumLength = length;}}return maxSumLength;}}

上一篇：數(shù)據(jù)結(jié)構(gòu)與算法–死磕二叉樹
下一篇：數(shù)據(jù)結(jié)構(gòu)與算法–二叉樹第k個(gè)大的節(jié)點(diǎn)

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法--再来聊聊数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。