考完研了秽土转生,开始刷一下LeetCode准备一下复试,我尽量每个工作日一更
题目描述
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
出处
思路
题目可以直接暴力做,如果想优于O(n^2)可以先排序然后用两个指针从首尾分别开始扫描。看评论区说可以用字典,做的时候没想出来。
代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int>nums1 = nums;
std::sort(nums.begin(), nums.end());
int h = 0;
int t = nums.size() - 1;
while (h != t) {
if (nums[h] + nums[t] == target) {
bool flag = false;
if(nums[h] == nums[t])
flag = true;
auto it1 = std::find(nums1.begin(), nums1.end(), nums[h]);
h = std::distance(nums1.begin(), it1);
vector<int>::iterator it2;
if(flag)
it2 = std::find(++it1, nums1.end(), nums[t]);
else
it2 = std::find(nums1.begin(), nums1.end(), nums[t]);
if (it2 != nums1.end()) {
t = std::distance(nums1.begin(), it2);
return vector<int>{h, t};
} else {
return vector<int>{};
}
} else if (nums[h] + nums[t] > target) {
t--;
} else {
h++;
}
}
return vector<int>{};
}
};