当前位置:网站首页>Sum of two numbers, sum of three numbers (sort + double pointer)
Sum of two numbers, sum of three numbers (sort + double pointer)
2022-07-05 23:02:00 【BugMaker-shen】
List of articles
One 、 And for s Two numbers of
Ascending , Use double pointer to traverse
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int l = 0;
int r = nums.size() - 1;
while(l < r){
if(nums[l] + nums[r] == target){
return {
nums[l], nums[r]};
}else if(nums[l] + nums[r] > target){
r--;
}else{
l++;
}
}
return {
};
}
};
Two 、 Sum of two numbers
And hash table storage has been traversed and not found and for target Number of numbers ,key Value ,value Subscript the element
use target Subtract the number of current traversals , Look up... In the hash table , Find it and return the current subscript (i) And the subscript taken from the hash table (target - nums[i]). If not, save the current element value and subscript in the hash table
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp; // mp[val] = index
for(int i = 0; i < nums.size(); i++){
if (mp.find(target - nums[i]) != mp.end()){
return {
i, mp[target - nums[i]]};
}else{
mp[nums[i]] = i;
}
}
return {
};
}
};
3、 ... and 、 Sum of three numbers
Sort with + The double pointer method , The time complexity is O ( N 2 ) O(N^2) O(N2)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end(), less<int>());
set<vector<int>> ans;
for(int l = 0; l < (int)nums.size() - 2 && nums[l] <= 0; l++){
int mid = l + 1;
int r = nums.size() - 1;
while(mid < r){
int sum = nums[l] + nums[mid] + nums[r];
if(sum == 0){
ans.insert({
nums[l], nums[mid], nums[r]});
r--;
while (mid < r && nums[r] == nums[r + 1]) r--; // while Circulation is used for weight removal
mid++;
while (mid < r && nums[mid] == nums[mid - 1]) mid++; // while Circulation is used for weight removal
}else if(sum > 0){
r--;
while (mid < r && nums[r] == nums[r + 1]) r--; // while Circulation is used for weight removal
}else{
mid++;
while (mid < r && nums[mid] == nums[mid - 1]) mid++; // while Circulation is used for weight removal
}
}
}
return vector<vector<int>> (ans.begin(), ans.end());
}
};
Four 、 The closest sum of three
unsorted , Direct violence backtracking , Overtime
class Solution {
public:
vector<int> choice;
int gap = INT_MAX;
int target_;
int ans;
void func(int i, const vector<int>& nums){
if(choice.size() == 3){
int sum = accumulate(choice.begin(), choice.end(), 0);
if (abs(target_ - sum) < gap) {
ans = sum;
gap = abs(target_ - sum);
}
}else{
for(int j = i; j < nums.size(); j++){
choice.push_back(nums[j]);
func(j + 1, nums);
choice.pop_back();
}
}
}
int threeSumClosest(vector<int>& nums, int target) {
target_ = target;
func(0, nums);
return ans;
}
};
Sort + Double pointer
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end(), less<int>());
long ans = INT_MAX;
for(int l = 0; l < (int)nums.size() - 2; l++){
int mid = l + 1;
int r = nums.size() - 1;
while(mid < r){
int sum = nums[l] + nums[mid] + nums[r];
if(abs(sum - target) < abs(ans - target)){
// sum and target Distance reduction of , Update ans
ans = sum;
}
if(sum == target){
// And for target, Then distance target lately , by 0, Returns the current sum
return sum;
}else if(sum > target){
r--;
}else{
mid++;
}
}
}
return ans;
}
};
边栏推荐
- 抖音__ac_signature
- Metasploit(msf)利用ms17_010(永恒之蓝)出现Encoding::UndefinedConversionError问题
- Leetcode weekly The 280 game of the week is still difficult for the special game of the week's beauty team ~ simple simulation + hash parity count + sorting simulation traversal
- 两数之和、三数之和(排序+双指针)
- VIM tail head intercept file import
- Overview of Fourier analysis
- Element positioning of Web Automation
- 基于STM32的ADC采样序列频谱分析
- Global and Chinese markets for reciprocating seal compressors 2022-2028: Research Report on technology, participants, trends, market size and share
- Tensor attribute statistics
猜你喜欢
实现反向代理客户端IP透传
[digital signal denoising] improved wavelet modulus maxima digital signal denoising based on MATLAB [including Matlab source code 1710]
2022 registration examination for safety management personnel of hazardous chemical business units and simulated reexamination examination for safety management personnel of hazardous chemical busines
Common JVM tools and optimization strategies
d3dx9_ How to repair 31.dll_ d3dx9_ 31. Solution to missing DLL
一文搞定JVM常见工具和优化策略
PLC编程基础之数据类型、变量声明、全局变量和I/O映射(CODESYS篇 )
鏈錶之雙指針(快慢指針,先後指針,首尾指針)
Ultrasonic sensor flash | LEGO eV3 Teaching
视频标准二三事
随机推荐
C Primer Plus Chapter 9 question 10 binary conversion
Three.JS VR看房
openresty ngx_lua请求响应
第一讲:蛇形矩阵
判断二叉树是否为完全二叉树
一文搞定JVM常见工具和优化策略
Detailed explanation of pointer and array written test of C language
Selenium+Pytest自动化测试框架实战
鏈錶之雙指針(快慢指針,先後指針,首尾指針)
Nanjing: full use of electronic contracts for commercial housing sales
d3dx9_ What if 29.dll is missing? System missing d3dx9_ Solution of 29.dll file
openresty ngx_lua正则表达式
使用rewrite规则实现将所有到a域名的访问rewrite到b域名
派对的最大快乐值
VOT toolkit environment configuration and use
分布式解决方案选型
openresty ngx_ Lua request response
傅里叶分析概述
一文搞定class的微观结构和指令
基于STM32的ADC采样序列频谱分析