1.15 数组双指针

[utterances-bot]

1.15 数组双指针

数组双指针知识 # 1. 双指针简介 # 双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问

https://algo.itcharge.cn/01_array/01_15_array_two_pointers/

[charles2268]

如果不相等，则将 slow 后移一位，-----------------------建议将“后移”一词改为"右移"，避免第一眼看上去疑惑

[itcharge]

如果不相等，则将 slow 后移一位，-----------------------建议将“后移”一词改为"右移"，避免第一眼看上去疑惑

已更正，感谢指正。

[weiyixing]

4.2 分离双指针伪代码模板 代码第7行有误 应该是+=1

[xuwkk]

4.4.3 解题思路中，4., 5. 中的nums1[left_2]应为nums1[left_1]。

[itcharge]

4.2 分离双指针伪代码模板 代码第7行有误 应该是+=1

感谢，已经更正，随后更新文章~

[itcharge]

4.4.3 解题思路中，4., 5. 中的nums1[left_2]应为nums1[left_1]。

感谢，已经更正，随后更新文章~

[YangYishe]

4.4.3 的思路, 时间复杂度O(n), 空间复杂度O(1)是怎么达成的?
就前面两行的排序代码, 想要时间复杂度O(n)就只能使用基数排序了吧? 但这样空间复杂度怎么能是O(n)内?

我实际写了一版, 复杂度倒是符合要求, 但并没有用到分离双指针的思想.

int[] temp=new int[1000];

        int resultCount=0;
        for(int n:nums1){
            if (temp[n]==0) {
                temp[n]=1;
            }
        }
        for(int n:nums2){
            if(temp[n]==1){
                temp[n]=2;
                resultCount++;
            }
        }

        int[] result=new int[resultCount];
        int resultIndex=0;
        for(int i=0;i<temp.length;i++){
            if(temp[i]==2){
                result[resultIndex++]=i;
            }
        }


        return result;

[HalfCheesee]

4.4.3 中排序的复杂度是O(n logn) 整体复杂度应该是O(nlogn)吧

[itcharge]

是的，复杂度应该是 $O(n \times \log n)$。
感谢指正～～

[cattytyty]

验证回文串的空间复杂度不是O(1)吗

[Wan-Yifei]

4.4.3 创建了新的List储存结果，空间复杂度难道不是O（n）吗？

[emmmdty]

4.4.3节的例题349 两个数组的交集，思路1的空间复杂度应该是O(n)吧

[itcharge]

感谢指正，复杂度已改为 $O(min(m,n))$。