【Leetcode第二周】两数之和(TwoSum)
程序员文章站
2024-03-08 19:34:52
...
题目:
https://leetcode-cn.com/problems/two-sum/solution/
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
思路:
我的思路是采用最简单的办法,遍历每一个元素,并查找之后的值是否有与其之和等于target。
这样的算法时间复杂度是O(n^2)。
代码:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
int size = nums.size();
if (size > 1) {
int num_1, num_2;
int index_1, index_2;//num_1,num_2的下标
index_1 = 0;
index_2 = 0;
int border = size - 1;
int sum = 0;
while (index_1 < border) {
num_1 = nums[index_1];
index_2 = index_1 + 1;
while (index_2 < size) {
num_2 = nums[index_2];
sum = num_1 + num_2;
if (sum == target) {
result = { index_1, index_2 };
return result;
}
else {
index_2 += 1;
//判断右移之后是否相等,相等则继续右移
while (index_2 < border && nums[index_2 - 1] == nums[index_2]) {
index_2 += 1;
}
}
}
index_1 += 1;
while (nums[index_1 - 1] == nums[index_1]) {
index_1 += 1;
}
}
}
return result;
}
};
在LeetCode上的测试结果: