LeetCode刷题（C++）——3Sum（Medium）

骑猪看日落 2022-06-16 04:06 157阅读 0赞

**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]
    ]

class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> result;
    		if (nums.empty())
    			return result;
    		sort(nums.begin(), nums.end());
    		for (int start = 0;start < nums.size();start++)
    		{
    			int i = start + 1;
    			int j = nums.size() - 1;
    			while (i < j)
    			{
    				if (nums[i] + nums[j] == -nums[start])
    				{
    					vector<int> temp;
    					temp.push_back(nums[start]);
    					temp.push_back(nums[i]);
    					temp.push_back(nums[j]);
    					result.push_back(temp);
    					while (i + 1 < nums.size() && nums[i] == nums[i + 1])
    						i++;
    					while (j - 1 >= 0 && nums[j] == nums[j - 1])
    						j--;
    					i++;
    					j--;
    				}
    				else if (nums[i] + nums[j] < -nums[start])
    					i++;
    				else 
    					j--;
    			}
    			while (start + 1 < nums.size() && nums[start] == nums[start + 1])
    				start++;
    		}
    		return result;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode 刷题

* [Leetcode 9. 回文数][Leetcode 9.] * [Leetcode 125. 验证回文串][Leetcode 125.] * [Leetc...

た入场券/ 2024年04月18日 12:09/ 0 赞/ 110 阅读

相关 leetcode刷题（3）

各位朋友们大家好，今天是我leedcode刷题系列的第三篇，废话不多说，直接进入主题。文章目录分割链表题目要求用例输入

古城微笑少年丶/ 2023年09月25日 23:08/ 0 赞/ 56 阅读

相关 LeetCode刷题（C++）——Next Permutation（Medium）

Implement next permutation, which rearranges numbers into the lexicographically next gre

布满荆棘的人生/ 2022年06月16日 07:40/ 0 赞/ 167 阅读

相关 LeetCode刷题（C++）——4Sum（Medium）

Given an array S of n integers, are there elements a, b, c, and d in S such that a \+ b

素颜马尾好姑娘i/ 2022年06月16日 07:11/ 0 赞/ 185 阅读

相关 LeetCode刷题（C++）——Edit Distance（Hard）

Given two words word1 and word2, find the minimum number of steps required to convert wo

╰半橙微兮°/ 2022年06月16日 06:49/ 0 赞/ 189 阅读

相关 LeetCode刷题（C++）——3Sum Closest（Medium）

Given an array S of n integers, find three integers in S such that the sum is closest to

深碍√TFBOYSˉ_/ 2022年06月16日 04:07/ 0 赞/ 183 阅读

相关 LeetCode刷题（C++）——3Sum（Medium）

Given an array S of n integers, are there elements a, b, c in S such that a \+ b \+ c =

骑猪看日落/ 2022年06月16日 04:06/ 0 赞/ 158 阅读

相关 LeetCode刷题（C++）——Course Schedule

There are a total of n courses you have to take, labeled from `0` to `n - 1`. Some cour

待我称王封你为后i/ 2022年06月10日 10:24/ 0 赞/ 169 阅读

相关 LeetCode刷题——Day3

6、将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 `"LEETCODEISHIRING"` 行数为 3 时，排列如下：

快来打我*/ 2022年03月27日 01:19/ 0 赞/ 268 阅读

相关 Leetcode刷题

39. 组合总和给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

秒速五厘米/ 2021年06月10日 20:37/ 0 赞/ 593 阅读