leetcode

类型1：两数之和

需要枚举数组中的两个元素时，如果发现随着第一个元素的递增，第二个元素是递减的，就可以使用双指针的方法

1. 两数之和

思路：
题目有两个关键点：1.无序数组，要输出坐标（因此要是想排序就得记录value-index的值了） 2.可有重复元素
快速查找—>哈希表

1. 暴力做法：遍历数组每个值，查找它后面的元素是否有配对的，O(n^2)
2. 哈希做法：暴力的改进点在于可以使用哈希表快速查找到是否有匹配元素.
   要注意！先判断map中是否有匹配元素，再加入到map中，避免和自己匹配

暴力是当前元素和后面的进行匹配，哈希做法是和前面的进行匹配，都肯定能匹配到的。因为两个匹配的元素肯定是一前一后，所以 前面的和后面的匹配 / 后面的和前面的匹配 肯定都行

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int len = nums.size();
        map<int, int> m;
        vector<int> res;
        for (int i = 0; i < len; i++) {
            if (m.count(target - nums[i]) > 0) {
                res.push_back(i);
                res.push_back(m[target - nums[i]]);
                return res;
            }
            // 先判断map，再insert进map，避免自己和自己匹配
            m[nums[i]] = i;
        }
        return res;
    }
};

167. 两数之和 II - 输入有序数组

思路：
关键点：1. 有序数组
要充分利用有序数组这一条件，利用双指针，left、right指向

代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int len = numbers.size();
        int l = 0, r = len - 1;
        vector<int> res;
        while (l < r) {
            if (numbers[l] + numbers[r] < target) {
                l++;
            } else if (numbers[l] + numbers[r] > target) {
                r--;
            } else {
                res.push_back(l + 1);
                res.push_back(r + 1);
                return res;
            }
        }
        return res;
    }
};

15. 三数之和

思路：
关键点：数组中包含重复数字，但输出结果不能重复，要通过while循环手动移指针到不重复的位置。
代码书写注意：1. 数组越界 2. 死循环
暴力做法中，有3重循环，对于每重循环，相邻两次枚举的元素不能相同，所以需要手动移指针的地方有3处
双指针做法中，第二三重循环符合，随着一个数的增加另一个数在减小，因此合并为一重循环，需要手动移指针的地方只有两处

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        vector<vector<int>> res;
        for (int i = 0; i < len; i++) {
            while (i > 0 && nums[i] == nums[i - 1]) {
                i++;
                // bug2 没加这条语句，数组越界
                if (i >= len) return res;
            }
            int l = i + 1;
            int r = len - 1;
            while (l < r) {
                if (nums[i] + nums[l] + nums[r] > 0) {
                    r--;
                } else if (nums[i] + nums[l] + nums[r] < 0) {
                    l++;
                } else {
                    res.push_back(vector<int>{nums[i], nums[l], nums[r]});
                    // bug3 数组越界，l < r是为了保证后面判断nums[l + 1]==nus[l]的数组不会越界
                    while (l + 1 < len && nums[l + 1] == nums[l]) l++;
                    // bug1 当没有相等时，忘记单给l++了，导致死循环
                    l++;
                    
                }
            }
        }
        return res;
    }
};

16. 最接近的三数之和

思路：找最接近的三数之和，当前和 > target ，需要 将和变小 才有可能找到更接近的。当前和 < target ，需要 将和变大 才有可能找到更接近的。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int len = nums.size();
        int resSum = 0x3f3f3f3f;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < len; i++) {
            int l = i + 1, r = len - 1;
            while (l < r) {
                int tmpSum = nums[i] + nums[l] + nums[r];
                if (abs(tmpSum - target) < abs(resSum - target)) {
                    resSum = tmpSum;
                }
                if (tmpSum < target) {
                    l++;
                } else if (tmpSum > target) {
                    r--;
                } else {
                    return resSum;
                }
            }
        }
        return resSum;
    }
};

中位数

---

1. multimap使用：

• 读取：没有重载operator[]，因为一个key可以对应多个value，也没法重载。
  读取方式：同一key对应的多个value都存在相邻的位置，使用multim.find(key)可以获得第一个interator
  for ( i < multim.count(key)) interator++; interator->second；
• 插入：multim.insert(make_pair(1,2))

2. 匿名vector vector{1, 2,3}