K-Sum

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. 思路： 排序，然后two pointer，复杂度 O(n^2) 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月13日 星期四 16时24分28秒 4File Name :16.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 int n; 11 int threeSumClosest(vector<int>& nums, int target) { 12 n = nums.size(); 13 sort(nums.begin(),nums.end()); 14 int mn = 0x3f3f3f3f; 15 int x,y,z; 16 for ( int i = 0 ; i <=n-3 ; i++) 17 { 18 int head = i+1; 19 int tail = n-1; 20 int tar = target - nums[i]; 21 while (head<tail) 22 { 23 int cur = target-nums[i]-nums[head]-nums[tail]; 24 if (abs(cur)<mn) 25 { 26 mn = abs(cur); 27 x = nums[i]; 28 y = nums[head]; 29 z = nums[tail]; 30 } 31 if (nums[head]+nums[tail]==tar) return target; 32 if (nums[head]+nums[tail]<tar) head++; 33 else tail--; 34 } 35 } 36 return x + y + z; 37 38 39 40 41 } 42 43};

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. 思路： O(n^2)枚举两个元素，变成2-sum问题，总体复杂度O(n^3)

Given an array S of n integers, are there elements a, b, c in S 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. 思路：排序O(nlgn)，然后枚举一个元素O(n)，对于每个元素，在剩下的区间中 two pointer O(n)