首页 > 代码库 > [leetcode]3Sum
[leetcode]3Sum
问题描述:
Given an array S of n integers, are there elementsa, 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.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
基本思路:
此题最naiev的做法是3层循环遍历所有可能的情况。此时时间复杂度是O(n^3);
较好的做法是对num数组排序。然后外层设置1层循环,内层即可看作求两个数的和为给定值的问题。(注意:此时的数组是有序的呦!较好的用好这个序关系就可以在O(n)的时间内解决2Sum问题。)。该方法最终的时间复杂度是O(n^2).
代码:
vector<vector<int> > threeSum(vector<int> &num) { //C++ vector<vector<int> > res; if (num.size() <= 2) return res; sort(num.begin(), num.end()); int twoSum; for (int i = 0; i < num.size() - 2;) { int l = i + 1, r = num.size() - 1; twoSum = 0 - num[i]; while (l < r) { if (num[l] + num[r] < twoSum) l++; else if (num[l] + num[r] == twoSum) { vector<int> three(3); three[0] = num[i]; three[1] = num[l]; three[2] = num[r]; res.push_back(three); do { l++; }while (l < r && num[l - 1] == num[l]); do { r--; }while (l < r && num[r + 1] == num[r]); } else r--; } do{ i++; }while (i < num.size() - 1 && num[i - 1] == num[i]); } sort(res.begin(),res.end()); return res; }
[leetcode]3Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。