3-sum
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:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
在一个数组中 ,num = -1 ,-2 ,1,2
找出 a b c in num ,并且 a+b+c = 0;方案的个数,并且打印出方案个数,(每个方案直接不重复)
最开始的代码 复杂度接近 o(n^3) ,数据一大就超时了
#include<iostream>#include<vector>#include<algorithm>#include<map>using namespace::std;class Solution {public: int threeSumClosest(vector<int> &num, int target) { // Start typing your C/C++ solution below // DO NOT write int main() function sort(num.begin(),num.end()); int sum = 0; int re = 0; int delta = 0x3fffffff; int len = num.size(); for(int i = 0 ; i < len - 2 ; i ++){ int l = i +1 ; int r = len -1; int pre = -1; int now = 1; while(l < r ){ sum = num[i] + num[l] + num[r]; if(sum == target) return target; else if(sum < target ){ if(abs(sum - target) < delta) delta = abs(sum - target),re = sum; l ++ ; } else{ if(abs(sum - target) < delta) delta = abs(sum - target) ,re = sum; r --; } } }//end for return re; }};