FB面经题，地里虽然很多人都提到了，但写清楚了的没几个。说明什么问题呢？就算题目都是tag题，都是高频面经题，能完美写出来问题都能答上的永远也都是少数人。不仅努力在刷，而且认真分析了思路，认真分析了时空复杂度了吗？

用List<Tuple(idx, val)>来表示两个sequence，只保留非零元素。搜索的时候类似merge two sorted list一样遍历两个list， 对于index相同的非零元素相乘。 follow up是如果一个 vector比另一个大得多怎么优化？那就是把非零元素储存成List of Tuple之后，遍历小的vector所对应的list, 然后在大的那个里面做binary search去找有没有这个index. 有的话就相乘。

class Tuple{
    int val,idx;
    Tuple(int val,int x){
        this.val=val;
        this.idx=idx;
    }
}
public int SparseVectorProduct(int[] a,int[] b){
    int res=0;
    List<Tuple> l1=new ArrayList<>();
    List<Tuple> l2=new ArrayList<>();
    for(int i=0;i<a.length;i++){
        if(a[i]!=0) l1.add(new Tuple(a[i],i));
    }
    for(int i=0;i<b.length;i++){
        if(b[i]!=0) l2.add(new Tuple(b[i],i));
    }
    int i = 0;
    int j = 0;
    while (i < l1.size() && j < l2.size()){
        while (l1.get(i).idx < l2.get(j).idx){
            i++;
        } 
        while (l1.get(i).idx > l2.get(j).idx){
            j++;
        }
        if (l1.get(i).idx == l2.get(j).idx){
            res += l1.get(i).val * l2.get(j).val;
            i++;
            j++;
        }
    }
    return res;
}

一大一小二分搜索:O(n*logm) n= l1.size(), m = l2.size()

int start = 0;
int end = l2.size() - 1;
for (Tuple t1 : l1){
    while (start + 1 < end){
        int mid = start + (end - 1)/2;
        if (l2.get(mid).idx == t1.idx){
            res += t1.val*l2.get(mid).val;
        } else if (l2.get(mid).idx > t1.idx){
            end = mid;
        } eles {
            start = mid;
        }
    }
}