欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【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上的测试结果:

【Leetcode第二周】两数之和(TwoSum)

相关标签: Leecode