首页 > 代码库 > 15. 3Sum
15. 3Sum
Problem statement:
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.
For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:[ [-1, 0, 1], [-1, -1, 2]]
Solution:
Which is different with 1. Two Sum, this question just need all three numbers whose sum is 0.
The basic idea:
- Sort this array by ascending order.
- Loop from the first element in array. it becomes a two sum problem. For i element, we should find two elements from rest of the array whose sum is -nums[i].
NOTE: In order to remove the duplicate element, we do duplication check when update the new value for the index, left and right pointers.
Time complexity O(n * n). Space complexity is O(1).
class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> triplet; // get the size of the array and convert it to integer type int size = nums.size(); for(int i = 0; i < size - 1; i++){ int left = i + 1; int right = size - 1; while(left < right){ // no need do duplicate check // For the same number, it will do same operation until it changes if(nums[left] + nums[right] == -nums[i]){ triplet.push_back({nums[i], nums[left], nums[right]}); // check for duplicated while(left < right && left + 1 < size && nums[left] == nums[left + 1]){ left++; } // check for duplicated while(left < right && right - 1 >= 0 && nums[right - 1] == nums[right]){ right--; } // normal pointers move left++; right--; } else if (nums[left] + nums[right] > -nums[i]) { right--; } else { left++; } } // remove duplicate candidates while(i + 1 < size && nums[i] == nums[i + 1]){ i++; } } return triplet; }};
15. 3Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。