447

题意

在平面上有n个整点，n<=500，在[-10000, +10000]范围内。求出下列三元组的个数：(i, j, k)，其中点i到j和i到k的距离相等。（顺序相关）

分析

我最开始是想把每两个点的距离都求出来，排序，然后在距离相同的二元组里寻找相同的点。但是这样其实太复杂了，也保证不了复杂度。于是我看了看解析（https://leetcode.com/problems/number-of-boomerangs/discuss/92866/C++-clean-solution-O(n2).-Fully-commented-and-explained.），发现了一种好得多的做法：

• 遍历每一个点
• 对于每一个点，建立一个map：<该点到其他点的距离, 点的数量>，也就是说，把其他所有点和它的距离建成一个map。可以这样做的核心是，我们只需要同样距离的点的数量
• 遍历这个map，得出以该点为开头的三元组共有多少个

一点细节：距离的平方最大为20000^2*2=800000000，不会超过int。

代码

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int ans = 0;
        
        for (int i = 0; i < points.size(); i++) {
            map<int, int> m;
            for (int j = 0; j < points.size(); j++) {
                if (i == j)
                    continue;
                int dis = (points[i].first - points[j].first) * (points[i].first - points[j].first) + (points[i].second - points[j].second) * (points[i].second - points[j].second);
                m[dis]++;
            }
            
            for (map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++) {
                if (iter->second > 1)
                    ans += iter->second * (iter->second - 1);
            }
        }
        
        return ans;
    }
};

时间大约是17.78%。因为马上就要面试，所以最近心急了。

560

题意

一个整数数组，长度<=20000，每个数的绝对值<=1000。给定数k，求出这个数组中全部值的和为k的子序列。

分析

十分简单。建立一个map，存放部分和。从第一个数开始累加，每得到一个部分和，就查看部分和-k在map中有几个；然后将该部分和存入map中。

代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0;
        int ans = 0;
        map<int, int> m;
        m[0]++;
        for(int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            ans += m[sum - k];
            m[sum]++;
        }
        return ans;
    }
};

时间是45.75%。

336

题意

给你一个数组的词（词之间两两不同），要求找到所有这样的词对：两个词拼在一起是回文词。

分析

开始时的想法是：两个词拼在一起能回文，说明比较短的那个词翻转之后是长的词的后缀。那么，把词按长度排序，然后把较短的词翻转之后插入到一个map中。

但这样似乎不好map。另一个想法是，把每个较短的词的前面的固定长度翻转之后进行map。但这样的话不好确定太短的词的长度。

另一个有趣的想法是，把所有的词都加入到map中，然后按词的长度倒排序，计算出最长的词的每个翻转之后对应的缺失部分，然后在map中查看有没有这样的词。很合理。于是我就这样做了。然后我发现根本没有排序的必要，不过两侧都要翻转。

有一些corner case，比如["a", ""]，需要输出[[0, 1], [1, 0]]。

代码

class Solution {
    
public:
    vector<vector<int>> palindromePairs(vector<string>& words) {
        map<string, int> mmap;
        for (int i = 0; i < words.size(); i++) {
            mmap[words[i]] = i;
        }
        
        vector<pair<int, int>> ans;
        
        for (int i = 0; i < words.size(); i++) {
            // flip and find a word that has length <=
            string rev = words[i];
            reverse(rev.begin(), rev.end());
            
            // cout << words[i] << ' ' << rev << endl;
            
            // flip to right
            for (int j = 0; j < rev.size(); j++) {
                if (j == 0 || words[i].substr(rev.size() - j, j) == rev.substr(0, j)) {
                    if (j != 0) {
                        // cout << words[i].substr(rev.size() - j, j) << ' ' << rev.substr(0, j) << endl;
                    }
                    if (mmap.count(rev.substr(j, rev.size() - j))) {
                        // cout << "right: " << j << ' ' << rev.substr(j, rev.size() - j) << endl;
                        int ind = mmap[rev.substr(j, rev.size() - j)];
                        if (ind != i)
                            ans.push_back(make_pair(i, ind));
                    }
                }
            }
            
            // flip to left
            for (int j = 0; j < rev.size(); j++) {
                if (j == 0 || rev.substr(rev.size() - j, j) == words[i].substr(0, j)) {
                    if (j != 0) {
                        // cout << rev.substr(rev.size() - j, j) << ' ' << words[i].substr(0, j) << endl;
                    }
                    if (mmap.count(rev.substr(0, rev.size() - j))) {
                        // cout << "left: " << j << ' ' << rev.substr(0, rev.size() - j) << endl;
                        int ind = mmap[rev.substr(0, rev.size() - j)];
                        if (ind != i)
                            ans.push_back(make_pair(ind, i));
                    }
                }
            }
            
            if (words[i] == rev && words[i].size() > 0 && mmap.count("")) {
                ans.push_back(make_pair(i, mmap[""]));
                ans.push_back(make_pair(mmap[""], i));
            }
        }
        
        sort(ans.begin(), ans.end());
        vector<pair<int, int>>::iterator iter = unique(ans.begin(), ans.end());
        ans.erase(iter, ans.end());
        vector<vector<int>> ret;
        for (int i = 0; i < ans.size(); i++) {
            vector<int> x;
            x.push_back(ans[i].first);
            x.push_back(ans[i].second);
            ret.push_back(x);
        }
        
        return ret;
    }
};

时间是29.94%。