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

素颜马尾好姑娘i 2022-06-16 07:11 167阅读 0赞

Given an array S of n integers, are there elements a, b, c, and d in S such that a \+ b \+ c \+ d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
    
    A solution set is:
    [
      [-1,  0, 0, 1],
      [-2, -1, 1, 2],
      [-2,  0, 0, 2]
    ]

class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int>> res;
    		if (nums.empty())
    			return res;
    		sort(nums.begin(), nums.end());
    		int len = nums.size();
    		for (int i = 0; i < len;i++) {
    			for (int j = i + 1;j < len;j++) {
    				int m = j + 1, n = len- 1;
    				while (m < n) {
    				    vector<int> v;
    					int sum = nums[i] + nums[j] + nums[m] + nums[n];
    					if (sum == target) {
    						v.push_back(nums[i]);
    						v.push_back(nums[j]);
    						v.push_back(nums[m]);
    						v.push_back(nums[n]);
    						res.push_back(v);
    						while (m + 1 < len&&nums[m] == nums[m + 1])
    							++m;
    						while (n > 0 && nums[n] == nums[n - 1])
    							--n;
    						++m;
    						--n;
    					}
    					else if (sum < target) {
    						while (m + 1 < len&&nums[m] == nums[m + 1])
    							++m;
    						++m;
    					}
    					else {
    						while (n > 0 && nums[n] == nums[n - 1])
    							--n;
    						--n;
    					}
    				}
    				while (j + 1 < len&&nums[j] == nums[j + 1])
    					++j;
    			}
    			while (i + 1 < len&&nums[i] == nums[i + 1])
    				++i;
    		}
    		return res;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 Leetcode 刷题

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

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

相关 leetcode刷题（4）

各位朋友们，大家好。这两天我将为大家分享我在学习栈的过程中遇到的题目，我们一起来看看。文章目录逆波兰表达式求值题目要求用例输入

ゞ浴缸里的玫瑰/ 2023年09月25日 23:32/ 0 赞/ 114 阅读

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

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

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

相关 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 赞/ 168 阅读

相关 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 赞/ 173 阅读

相关 LeetCode刷题（C++）——ZigZag Conversion（Medium）

The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows l

Bertha 。/ 2022年06月16日 03:22/ 0 赞/ 212 阅读

相关 LeetCode刷题（C++）——Sort List（Medium）

Sort a linked list in O(n log n) time using constant space complexity. / Defi

た入场券/ 2022年06月15日 01:19/ 0 赞/ 171 阅读

相关 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 赞/ 147 阅读

相关 LeetCode刷题——Day4

9、判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。示例 1: 输入: 121 输出: true 示例 2:

小鱼儿/ 2022年03月27日 10:26/ 0 赞/ 208 阅读

相关 Leetcode刷题

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

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