57. 三数之和

​​http://www.lintcode.com/zh-cn/problem/3sum/​​

相当于枚举一个数，然后在后面的一个有序数组中找到两个数和为x

可以用two pointer做，总复杂度n^2，O（1）的额外空间

一个数据，-5，2, 5, 7

要在里面找到和为7，第一次找到的会是2和7是不符合的，要contine

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

class Solution {
public:
    /*
     * @param numbers: Give an array numbers of n integer
     * @return: Find all unique triplets in the array which gives the sum of zero.
     */
    vector<vector<int>> threeSum(vector<int> &numbers) {
        // write your code here
        vector<vector<int>> ans;
        vector<int> vc;
        sort(numbers.begin(), numbers.end());
        map<vector<int>, bool> mp;
        for (int i = 0; i < numbers.size(); ++i) {
            int p1 = i + 1, p2 = numbers.size() - 1;
            if (i && numbers[i] == numbers[i - 1]) continue;
            int x = -numbers[i];
            while (p1 < p2) {
                while (p2 > p1 && numbers[p1] + numbers[p2] > x) --p2;
                while (p1 < p2 && numbers[p1] + numbers[p2] < x) ++p1;
                if (p2 == p1 || numbers[p1] + numbers[p2] != x) continue; //数据，判断
                ans.push_back(vector<int>{numbers[i], numbers[p1], numbers[p2]});
                int t = numbers[p1];
                while (p1 < p2 && numbers[p1] + numbers[p2] == x && numbers[p1] == t) {
                    ++p1, --p2;
                }
            }

        }
        return ans;
    }
};
int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif

    return 0;
}

View Code