2020-02-06 刷题3（数组）

217 存在重复元素

马上想到的就是用哈希表的做法，时间复杂度O(n), 空间复杂度O(n).
代码：

time: 25.03%, memory: 19.80%
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
    map<int, bool> ele_map;   // whether key exists
    int num_len = nums.size();
    for(int i = 0; i < num_len; i++){
        if (ele_map[nums[i]])
            return true;
        ele_map[nums[i]] = true;
    }
    return false;
}
};

还有一种很直觉的做法就是先排序，然后顺序查找。这种做法时间复杂度O(nlogn), 如果使用堆排序的话，空间复杂度就是O(1). 哈希表的方法，在n很大的时候，时间上会很有优势，n较小的时候，就要比排序慢。

136 只出现一次的数字

这个题目真的是非常的tricky啊。集合肯定是可以解的，但是空间复杂度O(n);哈希表也是可以的，空间复杂度也是O(n). 题干里，其他数都出现了两次，这个两次应该是可以利用的，应该可以想办法抵消掉，但是实在想不出来，不得已看了题解，太拍脑袋了
利用异或操作的特性：
a ^ 0 = a
a ^ a = 0
所以，所有的数顺序异或一遍，最后的值就是那个只出现一次的数。刚刚某人说，两个相等的数不挨着，先跟第三个数，最后还能是0吗？异或运算遵守交换律和结合律，是可以保证这一点的。
代码：

time: 96.44%, memory: 26.48%
class Solution {
public:
int singleNumber(vector<int>& nums) {
    int a = 0;
    for(int i = 0; i < nums.size(); i++){
        a = a ^ nums[i];
    }
    return a;
}
};

350 两个数组的交集 II

用了排序+双指针的做法。学会用while循环了，然后提交了几次疯狂报错，每次都是堆溢出，就是while的判断条件有问题。每个while循环都要判断两个下标是否越界，不能第一个操作i就不判断j，第二个操作j就不判断i，判断条件里&&后还是用到了取下标的操作，如果第一个循环里i已经超出范围了，第二个判断条件里j没有，那么i还是会越界。
时间复杂度：O(nlogn+mlogm), 空间复杂度：O(1)
本题最重要的就是，while循环的条件一定要写完整
代码：

time: 98.92%, memory: 56.01%
class Solution {
public:

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    int i = 0, j = 0;
    vector<int> intsec;
    while(i < nums1.size() && j < nums2.size()){
        while(i < nums1.size() && j < nums2.size() && nums1[i] < nums2[j])
            i++;
        while(i < nums1.size() && j < nums2.size() && nums2[j] < nums1[i])
            j++;
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]){
            intsec.push_back(nums1[i]);
            i++;
            j++;
        }
    }
    return intsec;
}
};

另一种解法是用哈希表，给第一个数组（最好取小的数组）设置一个哈希表，记录每个元素出现的次数，扫描大的数组，每出现一个哈希表中的键，值就减一。
时间复杂度：O(m+n), 空间复杂度: O(min(m, n))
这种方法对于如果两个数组大小差距很大，或者数组不能全部放到内存中的情况，是很有用的。