首页 > 代码库 > Leetcode 3Sum
Leetcode 3Sum
这题难度主要在如何避免重复上, 我们假设三个数的index分别为a, b, c
以下几种情况可能导致重复的产生
1. 第一个数导致的重复,num[a] == num[a-1], 后面相同的b,c的组合会导致答案重复一遍
2. 第二个数和第三个数导致的重复,重复只发生在找到一个答案以后,所以只需要确认b++,c--到一个不同的数就可以了
vector<vector<int>> threeSum(vector<int> &num) { int b, c, n = num.size(); vector<vector<int>> result; sort(num.begin(), num.end()); for(int i = 0; i < n-2; i++){ if(i > 0 && num[i] == num[i-1]) continue; b = i+1; c = n-1; while(b < c){ if(num[i] + num[b] + num[c] < 0) b++; else if(num[i] + num[b] + num[c] > 0) c--; else { vector<int> tmp; tmp.push_back(num[i]); tmp.push_back(num[b]); tmp.push_back(num[c]); result.push_back(tmp); b++;c--; while(num[b] == num[b-1]) // avoid duplicates b++; while(num[c] == num[c+1]) c--; } } } return result; }
Leetcode 3Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。