18. 4Sum
18
2023-09-11 14:22:48 时间
Given an array nums
of n integers and an integer target
, are there elements a, b, c, and d in nums
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.
Example:
Given array nums = [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] ]
AC code:
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { int len = nums.size(); vector<vector<int>> v; if (len < 4) return v; sort(nums.begin(), nums.end()); for (int i = 0; i < len-3; ++i) { if (i > 0 && nums[i] == nums[i-1]) continue; if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break; if (nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target) continue; for (int j = i+1; j < len -2; ++j) { if (j > i+1 && nums[j] == nums[j-1]) continue; if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break; if (nums[i] + nums[j] + nums[len-2] + nums[len-1] < target) continue; int left = j + 1; int right = len - 1; while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum > target) { right--; } else if (sum < target) { left++; } else { v.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]}); // don't use while statement. do { left++; } while (left < right && nums[left] == nums[left-1]); do { right--; } while (left < right && nums[right] == nums[right+1]); } } } } return v; } };
Runtime: 20 ms, faster than 75.88% of C++ online submissions for 4Sum.
相关文章
- Firefox 18 将支持 OS X 的视网膜屏
- uni-app:tabs切换页面之一(hbuilderx 3.6.18)
- 《从零开始学Swift》学习笔记(Day 18)——有几个分支语句?
- 小白学 Python 爬虫(18):Requests 进阶操作
- 18. 四数之和
- XSS-labs靶场实战(七)——第16-18关
- 【数据结构笔记18】数据结构之图的最短路径算法Floyd、有向无环图DAG、拓扑排序、关键路径
- AI如何提升10倍筛药效率?6月18日华为云携手中科院上海药物所揭开谜底
- [手游新项目历程]第18天-linux-protobuf+json
- LCP 18. 早餐组合
- CSharpGL(18)分别处理glDrawArrays()和glDrawElements()两种方式下的拾取(ColorCodedPicking)
- OpenMLDB Weekly Update(2021.10.11-2021.10.18)
- C++ Primer 学习笔记_44_STL实践与分析(18)--再谈迭代器【下】
- LCC编译器的源程序分析(18)函数定义
- Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined)
- mysql_18 _ 为什么这些SQL语句逻辑相同,性能却差异巨大