LeetCode: 3Sum

这一题的关键是不能用O(N^3)的算法，肯定会LTE，O(N^2)的算法在于里面一层用贪心的方法向中间逼近

逼近的速度可以用二分法优化，但是鉴于比较复杂这里就没写了

C++代码：

 1 class Solution {
 2  public:
 3      vector<vector<int> > threeSum(vector<int> &num) {
 4          // Start typing your C/C++ solution below
 5          // DO NOT write int main() function
 6          sort(num.begin(), num.end());
 7          vector<vector<int>> ret;
 8          vector<int> tmp;
 9          if (num.size() < 3) return ret;
10          for (int i = 0; num[i] <= 0 && i < num.size()-2; i++) {
11              int end = num.size()-1;
12              if (i > 0 && num[i] == num[i-1]) continue;
13              for(int beg = i+1; beg < end; beg++) {
14                  if (beg > i+1 && num[beg] == num[beg-1]) continue;
15                  int sum = num[i] + num[beg] + num[end];
16                  if (sum == 0) {
17                      tmp.clear();
18                      tmp.push_back(num[i]);
19                      tmp.push_back(num[beg]);
20                      tmp.push_back(num[end]);
21                      ret.push_back(tmp);
22                  }
23                  else if (sum > 0) end--, beg--;
24              }
25          }
26          return ret;
27      }
28  };

View Code

C#代码：

 1 public class Solution {
 2     public IList<IList<int>> ThreeSum(int[] nums) {
 3         IList<IList<int>> ans = new List<IList<int>>();
 4         Array.Sort(nums);
 5         if (nums.Count() < 3) return ans;
 6         for (int i = 0; i < nums.Count()-2; i++) {
 7             int end = nums.Count() - 1;
 8             if (i > 0 && nums[i] == nums[i-1]) continue;
 9             for (int beg = i + 1; beg < end; beg++) {
10                 if (beg > i + 1 && nums[beg] == nums[beg-1]) continue;
11                 int sum = nums[i] + nums[beg] + nums[end];
12                 if (sum == 0) {
13                     List<int> tmp = new List<int>(){nums[i], nums[beg], nums[end]};
14                     ans.Add(tmp);
15                 }
16                 else if (sum > 0) {
17                     end--;
18                     beg--;
19                 }
20             }
21         }
22         return ans;
23     }
24 }

View Code

Java:

 1 public class Solution {
 2     public List<List<Integer>> threeSum(int[] nums) {
 3         List<List<Integer>> ans = new ArrayList<List<Integer>>();
 4         Arrays.sort(nums);
 5         for (int i = 0; i < nums.length; i++)
 6         {
 7             if (i > 0 && nums[i] == nums[i-1])
 8                 continue;
 9             int left = i + 1;
10             int right = nums.length - 1;
11             while (left < right)
12             {
13                 if (left > i+1 && nums[left] == nums[left-1]) {
14                     left++;
15                     continue;
16                 }
17                 int sum = nums[i] + nums[left] + nums[right];
18                 if (sum == 0) {
19                     List<Integer> tmp = new ArrayList<Integer>();
20                     tmp.add(nums[i]);
21                     tmp.add(nums[left]);
22                     tmp.add(nums[right]);
23                     ans.add(tmp);
24                     left++;
25                 }
26                 else if (sum > 0) right--;
27                 else left++;
28             }
29         }
30         return ans;
31     }
32 }

View Code