数据结构与算法--再来聊聊数组

系统管理员 2023-01-23 14:48 88阅读 0赞

#### 再来聊聊数组 ####

*  这篇我们来总结一下数组相关的一些算法，数组的特点在于我们能通过下标得到对应数据，时间复杂度在O(1)，之前有多篇文章有数组相关的体系，一下来一个归纳：

[数据结构与算法–判断扑克牌是否顺子][Link 1]

[数据结构与算法–翻转单词顺序][Link 2]

[数据结构与算法–有序数组中找出和为s的两个数字][s]

[数据结构与算法–第一个只出现一次的字符][Link 3]

[数据结构与算法–数组中出一次的数字][Link 4]

[数据结构与算法–数字在排序数组中出现次数][Link 5]

[数据结构与算法–数组中的逆序对][Link 6]

[数据结构与算法–将数组排成最小的数][Link 7]

[数据结构与算法-- 数组中出现次数超过一半的数字（时间复杂度的讨论）][--]

[数据结构与算法–数组：二维数组中查找][Link 8]

[数据结构与算法–字符串的排列组合问题][Link 9]

[数据结构与算法–回朔，矩阵中查找字符串路径][Link 10]

[数据结构与算法–字符串：字符串替换][Link 11]

[数据结构与算法–查找与排序另类用法][Link 12]

[数据结构与算法–经典10大排序算法（动图演示）【建议收藏】][10]

*  以上是现阶段已经解除的数组相关，包括字符串其实也就是数组问题，其中用的最多的是双指针，还有就是归并法，二分法，其中排序是最重要的，在最后一排10大排序算法中详细介绍了每一种排序，并有动图演示。有的根据数组中数据的特殊性进行解题，例如出现一次的数字，利用位运算相关知识，还有排序算法思想的另类用法，利用排序思想进行查询。等，发现还是基础知识的运用最重要。
 *  以上文章中都与是运用数组进行解题，或者是其中有一个方法是用的数组。
 *  接下来是今天的题目：

#### 最长子串问题：给定一个字符串，找出字符串中的最长子串，使得这个子串中没有重复的数字 ####

*  因为写过之前的题目：有序数组中找出和为s的两个数字 ，我第一反应就是双指针遍历数组，分析如下：
    
     *  指针start，end都从0，开始，在end < length-1 情况下让end++
     *  判断当前指针范围内是否有重复数字，
     *  如果有，当前最长子串就是 maxTemp = start ~ end-1，先判断最长子串与当前maxTemp大小，取最大值，此时我们将start++
     *  如果没有重复数字，那么我们继续end++
     *  继续如上步骤，知道end = length-1 或者start > end
 *  以上遍历一次能得到最终值，但是在判断当前范围是否重复时候必然有额外开销，
    
     *  如果直接遍历判断，那么最终时间复杂度将会变成O(n2)
     *  我用空间换时间
        
         *  如果输入数据只有普通字符a~z，那么我们自建一个256 大小的hash表，用数组做容器
         *  如果输入数据中海油汉字等其他字符，那么我们只能用Map集合了，或者用链表自实现Map，在上文 数据结构与算法–第一个只出现一次的字符 我们就是如此实现
 *  如下动图：

![在这里插入图片描述][20210715182601578.gif]

*  如上分析有如下代码：

/** * 给定一个字符串，找出字符串中的最长子串，使得这个子串中没有重复的数字 * @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));
        }
        /** * 双指针实现滑动窗口，并空间换时间 * */
        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;
        }
    
    }

上一篇：[数据结构与算法–死磕二叉树][Link 13]  
下一篇：[数据结构与算法–二叉树第k个大的节点][k]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/118522294
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/118406709
[s]: https://blog.csdn.net/liaojiamin0102/article/details/118342126
[Link 3]: https://blog.csdn.net/liaojiamin0102/article/details/117775183
[Link 4]: https://blog.csdn.net/liaojiamin0102/article/details/118311083
[Link 5]: https://blog.csdn.net/liaojiamin0102/article/details/118191713
[Link 6]: https://blog.csdn.net/liaojiamin0102/article/details/117823999
[Link 7]: https://blog.csdn.net/liaojiamin0102/article/details/117705194
[--]: https://blog.csdn.net/liaojiamin0102/article/details/117356494
[Link 8]: https://blog.csdn.net/liaojiamin0102/article/details/109387663
[Link 9]: https://blog.csdn.net/liaojiamin0102/article/details/117223345
[Link 10]: https://blog.csdn.net/liaojiamin0102/article/details/115149833
[Link 11]: https://blog.csdn.net/liaojiamin0102/article/details/109478169
[Link 12]: https://editor.csdn.net/md/?articleId=114856118
[10]: https://editor.csdn.net/md/?articleId=109512635
[20210715182601578.gif]: /images/20221004/92c74fdad5f34f7586a0f9ea03f43b41.png
[Link 13]: https://blog.csdn.net/liaojiamin0102/article/details/118699552
[k]: https://blog.csdn.net/liaojiamin0102/article/details/118796502