3Sum(or k_Sum)

来源：cnblogs　　作者：康托漫步　　时间：2018/9/25 19:24:46　　对本文有异议

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
 
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
(4Sum问题)
C++:

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