首页 > 代码库 > LeetCode-3Sum -三数求和-有序数组扫描

LeetCode-3Sum -三数求和-有序数组扫描

https://oj.leetcode.com/problems/3sum/

先排序。然后枚举i属于[0,n-3]的这些数作为三元组的第一个数,令x=0-a[i]。这样就变成从[i+1,n)找出两个数加起来和等于x。

由于这些数是有序数,可以使用l,r指针对在两侧向中间逼近。这利用了一个事实:如果al+ar=x;对于l‘<l,r‘<r,则一定由al‘+ar‘<x。右边也是一样,所以可以这样向中间逼近的查找。

另外要注意答案需要去除重复。

typedef pair<int,pair<int,int>> scpair;class Solution {public:    int m,n;    vector<vector<int> > threeSum(vector<int> &num) {        n=num.size();        vector<vector<int> > res;        if (n<3) return res;        vector<int> &a=num;        set   <scpair> st;        sort(a.begin(),a.end());        for (int i=0;i<n-2;i++) {            scpair cr;            cr.first=a[i];            int l=i+1;            int r=n-1;            int x=0-a[i];            while(l<r){                int cs=a[l]+a[r];                if (cs<x) l++;                else if(cs>x) r--;                else {                    cr.second.first =a[l];                    cr.second.second=a[r];                    st.insert(cr);                    l++;                }            }        }        for (auto it=st.begin();it!=st.end();it++) {            vector<int> cur(3,0);            cur[0]=it->first;            cur[1]=it->second.first;            cur[2]=it->second.second;            res.push_back(cur);        }        return res;    }};

 

LeetCode-3Sum -三数求和-有序数组扫描