不如这样：

public static int[] intersectSortedArrays(int[] a, int[] b){
    int[] c = new int[Math.min(a.length, b.length)]; 
    int ai = 0, bi = 0, ci = 0;
    while (ai < a.length && bi < b.length) {
        if (a[ai] < b[bi]) {
            ai++;
        } else if (a[ai] > b[bi]) {
            bi++;
        } else {
            if (ci == 0 || a[ai] != c[ci - 1]) {
                c[ci++] = a[ai];
            }
            ai++; bi++;
        }
    }
    return Arrays.copyOfRange(c, 0, ci); 
}

从概念上讲，它与您的类似，但包含了许多简化。
我不认为你能改进时间复杂度。

**edit：**我已经试过这段代码，它通过了所有的单元测试。

这个问题本质上简化为一个 join 操作，然后是一个 filter 操作（删除重复项，只保留内部匹配）。
由于两个输入都已经排序，所以可以通过merge join高效地实现连接，具有O（size（a）+ size（b））。
因为连接的输出是排序的，所以 filter 操作是O（n）的，而要删除重复项，您所要做的就是检查每个元素是否与它前面的元素相同。只过滤内部匹配项是微不足道的，您只需丢弃任何不匹配的元素（外部连接）。
并行性（在连接和过滤器中）有机会获得更好的性能，例如Hadoop上的Apache Pig框架提供了合并连接的parallel implementation。
在性能和复杂性（以及可维护性）之间存在着明显的权衡，所以我认为面试问题的一个好答案确实需要考虑性能需求。

• 基于集合的比较- O（nlogn）-相对较慢，非常简单，如果没有性能问题就使用。
• 合并连接+过滤- O（n）-快速，容易出现编码错误，如果性能有问题就使用。理想情况下，尝试利用现有库来完成此操作，或者甚至使用数据库（如果合适）。
• 并行实施- O（n/p）-非常快，需要其他基础架构就位，在卷非常大并且预计会增长时使用，这是一个主要的性能瓶颈。

(Also注意问题中的函数 intersectSortedArrays 本质上是一个修改过的合并连接，其中过滤是在连接过程中完成的。2你可以在没有性能损失的情况下进行过滤，尽管稍微增加了内存占用）。

• 最后的想法 *

事实上，我怀疑大多数现代商业RDBMS在它们的连接实现中提供线程并行性，所以Hadoop版本提供的是机器级并行性（分布）。从设计的Angular 来看，也许一个好的、简单的解决方案是将数据放在数据库中，在A和B上建立索引（有效地排序数据），并使用SQL内部连接。

使用数组列表存储结果。

public ArrayList<Integer> arrayIntersection(int [] a, int[] b)
{
    int len_a=a.length;
    int len_b=b.length;
    int i=0;
    int j=0;
    ArrayList<Integer> alist=new ArrayList();

    while(i<len_a && j<len_b)
    {
        if(a[i]<b[j])
            i++;
        else if(a[i]>b[j])
            j++;
        else if(a[i]==b[j])
        {
            alist.add(a[i]);
            i++;
            j++;

        }
    }

   return alist;    
  }

如果你使用的是'Integer'（对象）数组，并希望使用java API方法，你可以检查下面的代码。注意，下面的代码可能比上面列出的原语方法更复杂（因为它使用了一些从一个数据结构到另一个数据结构的转换逻辑）和内存消耗（因为使用了对象）。我刚刚试过（shrugs）：

public class MergeCollections {
    public static void main(String[] args) {
        Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13};

        Set<Integer> intSet1 = new TreeSet<Integer>();
        intSet1.addAll(Arrays.asList(intArray1));
        intSet1.addAll(Arrays.asList(intArray2));
        System.out.println(intSet1);
    }
}

并且输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13]

此外，请检查此链接：Algolist - Algo to merge sorted arrays

编辑：已将散列集更改为树集
EDIT 2：现在问题已编辑完毕，我将添加一个简单的解决方案来查找交集：

public class Intersection {
    public static void main(String[] args) {
        Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13};

        List<Integer> list1 = Arrays.asList(intArray1);
        Set<Integer> commonSet = new TreeSet<Integer>();
        for(Integer i: intArray2) {
            if(list1.contains(i)) {
                commonSet.add(i);
            }
        }

        System.out.println(commonSet);
    }
}

我不知道这样解决这个问题是否是个好主意：
说

A,B are 1 based arrays
    A.length=m
    B.length=n

1)初始化长度为min（m，n）数组C
2)通过检查第一个和最后一个元素，只关注公共部分。这里可以使用二进制搜索。举个例子来保存一些单词：

A[11,13,15,18,20,28,29,80,90,100.........300,400]
    ^                                          ^
 B[3,4,5,6,7.8.9.10.12,14,16,18,20,..400.....9999]
                     ^                ^

then we need only focus  on

    A[start=1](11)-A[end=m](400)
    and
    B[start=9](12)-B[end](400)

3).比较两个数组的 range(end-start)。取 range 较小的数组，比如A，对于A[start] ~ A[end]中的每个元素A[i]，在B[start,end]中进行二进制搜索，

• 如果找到，则将元素放入C，重置B。开始到foundIdx+1，
• 否则，将B.start设置为最小元素[j]，其中B[j]大于A[i]，以缩小范围

4)继续3）直到处理完A[start，end]中的所有元素。

• 通过步骤1，我们可以找到两个数组之间没有交集的情况。
• 在步骤3中进行二分查找时，我们比较A[i]和A[i-1]，如果相同，则跳过A[i]。

这样，如果（A和B相同），最坏情况是lg（n！）？2不确定。
平均病例？

以下是记忆力的提升：
最好存储您的结果（C）在动态结构中，如链表，找到相交元素后创建一个数组（就像处理数组r一样）。如果A和B的数组非常大，并且期望公共元素比较少，那么这种技术将特别好（当你只需要很小的内存时，为什么要搜索一大块连续的内存呢？）。
编辑：还有一件事我会改变，这可能有点吹毛求疵，那就是当最坏情况的迭代次数事先知道时，我会避免使用无绑定循环。

public static int[] getIntersectionOfSortedArrays(int[] numbers1, int[] numbers2) {
    var size1 = numbers1.length;
    var size2 = numbers2.length;

    var elementsCount = Math.min(size1, size2);
    var result = new int[elementsCount];

    var i1 = 0;
    var i2 = 0;
    var index = 0;

    while (i1 < size1 && i2 < size2) {
        if (numbers1[i1] == numbers2[i2]
                && (index == 0 ||  numbers1[i1] != result[index - 1])) {
            result[index] = numbers1[i1];
            i1++;
            i2++;
            index++;
        } else if (numbers1[i1] > numbers2[i2]) {
            i2++;
        } else {
            i1++;
        }
    }

    return Arrays.copyOf(result, index);
}