Fork me on GitHub

3-sum-closest

Posted on | In

Question

Analysis

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution{
public:
  vector <vector <int>> threeSum (vector <int> & num)
  {
    vector <vector <int>> result;
    if (num.size()<3) return result;
    int ans=0;
    sort (num.begin(),num.end());
    for (int i=0;i<num.size()-2;++i)
    {
      if (i>0 && num[i]==num[i-1])
        continue;
      int j=i+1;
      int k=num.size()-1;
      while(j<k)
      {
        ans=num[i]+num[j]+num[k];
        if (ans==0)
        {
          result.push_back({num[i],num[j],num[k]});
          ++j;
          while (j<num.size() && num[j]==num[j-1])
            ++j;
          --k;
          while(k>=0 &&num[k]==num[k+1])
            --k;
         }
         else if (ans>0)
           --k;
         else
           ++j;
      }
    }
    return result;
  }
};

参考：https://www.kancloud.cn/kancloud/data-structure-and-algorithm-notes/72956