由LeetCode 1.Two Sum引起的几个问题

LeetCode 1.Two Sum

Description:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Difficulty: Easy

---

分析：

此题比较容易，如果不是很注重时间复杂度的话，直接一个时间复杂度O(n^2)的算法就搞定了，该算法两次循环遍历vector，由于明确表示有且只有一个解，开一个vector记录下符合题意的nums的下标即可。

代码如下

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> ans(2);
		for (int i = 0; i < nums.size(); i++) {
			for (int j = i + 1; j < nums.size(); j++) {
				if (nums[i] + nums[j] == target) {
					ans[0] = i;
					ans[1] = j;
					return ans;
				}
			}
		}
		return vector<int>({low, high});// c++11
	}
};
// 测试
int main() {
	Solution s;
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	int target;
	cin >> target;
	cout << "[" << s.twoSum(nums, target)[0] << ", " << s.twoSum(nums, target)[1] << "]" << endl;
	return 0;
}

---

Similar Questions

167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Difficulty: Easy

---

分析：

乍一看，和前面的Two Sum基本一样，如果不需要注意时间复杂度的话，直接把ans[0] = i改成ans[0] = i + 1，把ans[1] = j + 1就可以解决该问题了。
但是，哪里能这么容易AC呢，这样交上去当然超时了。
所以，我们有了一个更好的算法，注意到题意表明该vector是一个升序的数组，因此，我们可以构造出一个O(n)的算法：从vector两头，即从小端从大端两边开始相加，如果和大于target，则大端减1，如果和小于target，则小端加1，相等则跳出循环，返回结果为下标加1。

代码如下

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		/*超时
		vector<int> ans(2);
		for (int i = 0; i < nums.size(); i++) {
			for (int j = i + 1; j < nums.size(); j++) {
				if (nums[i] + nums[j] == target) {
					ans[0] = i + 1;
					ans[1] = j + 1;
					return ans;
				}
			}
		}*/
		int low = 0, high = nums.size() - 1;
		while (nums[low] + nums[high] != target) {
			if (nums[low] + nums[high] < target) low++;
			else high--;
		}
		return vector<int>({low + 1, high + 1});// c++11
	}
};
int main() {
	Solution s;
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	int target;
	cin >> target;
	cout << "[" << s.twoSum(nums, target)[0] << ", " << s.twoSum(nums, target)[1] << "]" << endl;
	return 0;
}

---

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Difficulty: Easy

---

分析：

首先，根据题意得知这是一颗二叉排序树，即左子树节点的值均小于根节点的值，右子树节点的值均大于根节点的值。
因此，我们可以利用上面167题同样的解法，先把该二叉排序树用vector经过中序遍历存起来，即可得到升序的一个vector，然后根据小端大端两端同时遍历即可得到解。

代码如下：

class Solution {
public:
	bool findTarget(TreeNode* root, int k) {
		vector<int> nums;
		inorder(root, nums);
		int i = 0, j = nums.size() - 1;
		while (i < j) {
			if (nums[i] + nums[j] == k) return true;
			(nums[i] + nums[j] < k) ? i++ : j--;
		}
		return false;
	}
	// 将树的值放进vector里面，转换成167的处理方式
	void inorder(TreeNode* root, vector<int>& nums) {
		if (root == NULL) return;
		inorder(root->left, nums);
		nums.push_back(root->val);
		inorder(root->right, nums);
	}
};

另外一种解法：

参考原题的一个讨论，里面说到这么一种算法：开一个set存放已遍历的root，判断target减去当前遍历的root的值是否存在于set集合中，如果有，则返回true。

代码如下：

#include <set>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Solution {
public:
	bool findTarget(TreeNode* root, int k) {
		unordered_set<int> set;
		return dfs(root, set, k);
	}
	bool dfs(TreeNode* root, unordered_set<int>& set, int k) {
		if (root == NULL) return false;
		if (set.count(k - root->val)) return true;
		set.insert(root->val);
		return dfs(root->left, set, k) || dfs(root->right, set, k);
	}
};